#StackBounty: #algorithm Best time to buy and sell stocks when allowing consecutive buys or sells

Bounty: 100

Problem

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.

Example 1:

Given a = [1,2,10,9], return 16

Explanation:

You can buy on day 1 and 2 and sell on day 3 and 4.

Profit: -1-2+10+9 = 16

Example 2:

Given a = [9,5,9,10,5], return 5

Explanation:

You can buy on day 2 and sell on day 4.

Profit: -5 + 10 = 5

My analysis

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.

Question

How could this be solved with a better time complexity, such as O(nlogn)?


Get this bounty!!!

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.