Selling Stock
You have been given stock values/prices for N number of days. Every i-th day signifies the price of a stock on that day. Your task is to find the maximum profit which you can make by buying and selling the stocks.

Note :

You may make as many transactions as you want but can not have more than one transaction at a time i.e, if you have the stock, you need to sell it first, and then only you can buy it again.

Input format :

The first line contains an integer 't' which denotes the number of test cases or queries to be run. Then the test cases follow. The first line of each test case or query contains an integer 'N' representing the total number of days for which you have stock prices. The second line contains 'N' single space-separated integers representing the price of the stock on i-th day.

Output Format :

For each test case, print the maximum profit that you can earn. Output for every test case will be printed in a separate line.

Note :

You are not required to print anything explicitly. Just implement the function.

Constraints :

1

Question

Selling Stock

You have been given stock values/prices for N number of days. Every i-th day signifies the price of a stock on that day. Your task is to find the maximum profit which you can make by buying and selling the stocks.

Note :

You may make as many transactions as you want but can not have more than one transaction at a time i.e, if you have the stock, you need to sell it first, and then only you can buy it again.

Input format :

The first line contains an integer 't' which denotes the number of test cases or queries to be run. Then the test cases follow.

The first line of each test case or query contains an integer 'N' representing the total number of days for which you have stock prices.

The second line contains 'N' single space-separated integers representing the price of the stock on i-th day.

Output Format :

For each test case, print the maximum profit that you can earn.

Output for every test case will be printed in a separate line.

Note :

You are not required to print anything explicitly. Just implement the function.

Constraints :

1 <= t <= 10^2
0 <= N <= 10^5
Time Limit: 1 sec

Accepted Answer

Brute Force Approach

Let's say we have stock values of two days, say, [20, 30].

One must have to buy the stock first in order to sell it in the coming days.

So,

1. if I choose to buy the stock on first day for a value of 20 and sell it on the second day for a value of 30, I can earn a max profit of 10.

2. If I chose to skip day 1, then buying the stock on day 2 will put me in lose since there are no further days on which I can sell the stock. Hence, in this case, day 2 has to be skipped in order to make a max profit of 0.

Among these two scenarios, the first case yields me maximum profit and hence the answer.

This means, for every day, I may choose to buy or skip the stock. Once bought, I have to sell it in the following days to yield a max profit. Hence, to explore all the different possibilities,

We run a loop indicating the buying day. For every day when a stock is bought,
We run a nested loop to try all the combination of days on which the stock was sold.
1. If the value of the stock on buying day is less than the value of the stock on the day bought, we have a profit.
2. Recursively get the value of profit for the rest of the values assuming neither the stocks were bought and nor were the sold.
Get the max profit value out of all the combinations.

Space Complexity: O(1)Explanation:

O(N), Where N is the total number of days

Since at any time the maximum functions call that would exist in the stack will be N

Time Complexity: O(1)Explanation:

O(N ^ N), Where N is the total number of days

Since for every index, you recurse on the array from that index till the end

Accepted Answer

Local Minima/Maxima Approach

Keep a ‘profit’ variable to keep track of the total profit earned
Check the stock prices of every two consecutive days with a loop
1. If the price on the second day is more than that of the first day, add their price's difference to ‘profit’
Return profit

Space Complexity: O(1)Explanation:

O(1).

Since no extra chunk of memory is used.

Time Complexity: O(n)Explanation:

O(N).

Only a single pass through the array is needed to get the answer

You have been given stock values/prices for N number of days. Every i-th day signifies the price of a stock on that day. Your task is to find the maximum profit which you can make by buying and selling the stocks.

Note :

Input format :

Output Format :

Note :

Constraints :

Top Nagarro Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Nagarro Software Developer