Best Time to Buy and Sell

Moderate

0/80

Average time to solve is 20m

Contributed by

17 upvotes

+12 more companies

Problem statement

Note:

You must sell the stock before you buy it again.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains an integer value N, denoting the size of the input array.

The second line contains N single space-separated integers, denoting the prices on each day.

Output Format:

The only output line contains an integer, denoting the maximum profit.

Note:

You are not required to print the output, it has already been taken care of. Just implement the function.

Constraints:

1 <= N <= 5 * 10^4
0 <= PRICES[i] <= 10^4    

Time Limit: 1sec

Sample Input 1:

6
2 4 7 1 3 5

Sample Output 1:

Explanation for Sample Input 1:

As we are allowed to do any number of transactions to maximize the profit,
The first transaction we will do is to buy on day 1 (PRICE = 2) and sell on day 3 (PRICE = 7), making a profit of  5 (7 - 2).
The second transaction we will do is to buy on day 3 (PRICE = 1) and sell on day = 6 (PRICE = 5), making a profit of 4 (5 - 1).
Total profit = 5 + 4 = 9.

Sample Input 2:

4
1 2 3 4

Sample Output 2:

Console