You’re given the n stock prices for n days. Output the maximum profit you can reach by trading stocks. You can only trade at most once a day: on each day you can choose to either buy a single stock, or sell a single stock (if you have one), or give up the trade for that day and do nothing.
a = [1,2,10,9], return
You can buy on day 1 and 2 and sell on day 3 and 4.
Profit: -1-2+10+9 = 16
a = [9,5,9,10,5], return
You can buy on day 2 and sell on day 4.
Profit: -5 + 10 = 5
The difficult part is that you can engage in consecutive buys and/or sells, meaning that once you posses a stock, you don’t necessarily have to sell it before buying another one.
My idea is the following algorithm:
Start from the largest price, and then match the smallest price that occurs before that maximum price in the input array. After matching, remove these two prices from the array and keep repeating this process until you can find no more match. It seems like this algorithm works, but it costs O(n2) time, which is not fast enough.
How could this be solved with a better time complexity, such as O(nlogn)?