2

Buy and Sell Stock - III

Difficulty: EASY
Contributed By
Shivam |Level 1
Avg. time to solve
10 min
Success Rate
90%

Problem Statement

You can perform a transition with these conditions -

``````1. Not allowed to engage in more than 1 transaction at a time, which means if you have bought stock then you can buy another stock before selling the first stock.

2. If you bought a stock at ‘X’ price and sold it at ‘Y’ price then the profits ‘Y - X’.
``````
Note:
``````It is not compulsory to perform an exact '2' transaction.
``````
Input format:
``````The first line of input contains an integer 'T' denoting the number of test cases.

The first line of each test case contains a single integer 'N', 'N' denotes the length of array ‘prices’.

The second line of each test case contains an 'N' space-separated integers, in which every integer denotes an element of the array "prices".
``````
Output Format
``````For each test case, you need to print the maximum profit made by selling the stocks.
``````
Note :
``````You do not need to print anything; it has already been taken care of.
``````
Constraints:
``````1 <= T <= 50
1 <= N <= 10^4
0 <= A[i] <= 10^9

Time limit: 1 second
``````
Sample Input 1:
``````2
7
3 3 5 0 0 1 4
6
1 2 3 3 6 9
``````
Sample Output 1:
``````6
8
``````
Explanation For Sample Input 1:
``````Test Case 1:
``````

``````Buy the first stock at ‘0-th’ day and sell at ‘2-nd’ day - ‘profit = 5 - 3 = 2’
Buy the second stock at ‘4’th day and sell at ‘6’th day - ‘profit = 4 - 0 = 4’
Total profit ‘2 + 4 = 6’.

Test Case 2:
``````

``````Buy the stock at ‘0’ day and sell at ‘5’ day - ‘profit = 9 - 1 = 8’.

Suppose we bought the first stock at ‘0-th ‘ day and sold at ‘2-nd’ then the profit will be ‘3 - 1 = 2’ and second stock at ‘3-rd’ day and sold at ‘5-th’ day then the profit will be ‘9 - 3 = 6’  so total profit ‘2 + 6 = 8’.
But there is no other possibility to get more profit than ‘8’.
``````
Sample Input 2:
``````2
5
1 2 4 3 2
4
9 8 7 6
``````
Sample Output 2:
``````3
0
``````
Console