Find the maximum profit if given an array of daily stock prices and allowed to buy and sell twice

Question

I am wondering about the correctness of this method:

We are given a function / algorithm findMaxProfit() that can find the maximum profit when given an array of stock prices, and buy and sell once, with time complexity O(n), additional space complexity O(1). The buy must occur before the sell (meaning no short sell is allowed).

findMaxProfit() will return the maximum profit, and the buy and sell point (as indexes into the array). Example: [3200, 6, 22] meaning max profit is 3200, and buy on day 6, sell on day 22. (day in the description is also 0 index based).

Any buy and sell can occur on the same day, meaning profit = 0.

Now, find the maximum profit if you are allowed to buy and sell at most twice, with the second buy occurring on or after the first sell, and with time complexity O(n), additional space complexity O(1).

I think one assumption is that we buy the same number of shares both times (let's say just 1 share). Otherwise, if the earned money from the first time can be used to buy stocks the second time, then it is not the dollar amount we are concerned with, but the percentage gain overall.

// this function just returns the max profit, no need to return the 
// buy / sell point.  In JavaScript ES6

function findMaxProfitBuySellTwice(arr) {
  const [max1, a, b] = findMaxProfit(arr);

  return max1 + Math.max(findMaxProfit(arr.slice(0, a), 
                         findMaxProfit(arr.slice(b + 1));
}

the a can be a + 1, while the b + 1 can be b, but with no use. The reason is let's say if you buy on day 6, then from day 5 to day 6, there will be no profit, or else the findMaxProfit() would have included day 5. Likewise, if findMaxProfit() says to sell on day 22, then from day 22 to 23, there is no profit, so we really don't need to start at day 22 but start at day 23. slice() will return empty array if it is out of bound.

About the correctness of the code, because the Maximum Stock Profit Problem is interchangeable with the Maximum Subarray Problem. In fact, the number returned by the Maximum Stock Profit Problem and the number returned by the Maximum Subarray Problem should actually be exactly the same number.

So if we are asked to find the 2 subarrays that will add up to maximum, we could do the same as above: (1) find the maximum subarray first. (2) now slide this region out, and find the max for the remaining two regions. (3) just add up the max from step (1) and the maximum of the 2 numbers from step (2).

It seems the correctness of doing this to the Maximum Subarray Problem is more obvious: the 2 maximum subarrays are just finding the max first, and then disregard this region, and find the max of the remaining 2 sets of data.

Note that the Maximum Stock Profit Problem and the Maximum Subarray Problem should be able to convert to each other, say, from the stock problem to the subarray problem by taking the difference between the daily prices (resulting an array with size 1 less in general):

function convertStockDataToMaxSubarrayData(arr) {

  var maxSubarrayData = [], i;

  if (arr.length <= 1) return [];

  for (i = 1; i < arr.length; i++) {
    maxSubarrayData.push(arr[i] - arr[i-1]);
  }

  return maxSubarrayData;
}

Answer 1

It seems the correctness of doing this to the Maximum Subarray Problem is more obvious: the 2 maximum subarrays are just finding the max first, and then disregard this region, and find the max of the remaining 2 sets of data.

That's actually wrong. Let the array be [2, -1, 4, 2, 3]. Your solution would take the whole array as the maximum during the first step (the sum is 11) and remove it, leaving an empty array, so it would return 11. But that's not correct. Two subarray [0, 1) and [2, 5) add up to 12, yielding an optimal solution.

It also implies that your solution to the stock selling problem is also incorrect (a counter example can be constructed in a similar manner).

You can use dynamic programming to solve the problem correctly. There's a constant number of states in each layer, so the extra space complexity is constant (the code is in python, but it should be easy to implement this algorithm in any other language):

def get_two_max(nums):
    """
    Returns the two maximums in the list.
    The list must contain at least 2 elements.
    """
    max1 = max(nums[0], nums[1])
    max2 = min(nums[0], nums[1])
    for num in nums[2:]:
        if num >= max1:
            max2 = max1
            max1 = num
        elif num > max2:
            max2 = num
    return max1, max2


def get_max_two_subarrays(nums):
    """
    Returns the maximum sum of two non-intersecting non-empty subarrays
    """
    if len(nums) < 2:
        # There're no two non-intersecting non-empty subarrays
        return None
    count_non_neg = sum(1 for num in nums if num >= 0)    
    if count_non_neg < 2:
        # There is at most one positive element, so the optimal answer is 
        # to take two largest elements of the array
        return sum(get_two_max(nums))
    # The state has the following meaning:
    # 0 - the first subarray hasn't started
    # 1 - the first subarray has started, but it's not over yet
    # 2 - the first subarray is over
    # 3 - the second subarray has started, but it's not over yet
    # 4 - both subarrays are over
    dp = [0] * 5
    for num in nums:
        new_dp = [0] * len(dp)
        for state in range(len(dp)):
            # Doesn't change the state. Adds the current element if one of
            # the subarrays is not over.
            new_dp[state] = max(new_dp[state], dp[state] + (num if state % 2 else 0))
            if state + 1 < len(dp):
                # Goes to the next state by opening/closing a subarray
                new_dp[state + 1] = max(new_dp[state + 1], new_dp[state])
        dp = new_dp
    # The answer is the value of the state when both subarrays are over
    return dp[-1]

If you have a solution and you're not sure if it's correct or not, you can do the following:

1. Implement a slow but obviously correct solution (in this case, it would just generate all subarrays, compute their sums and choose the best one).

2. Generate thousands of small test cases and compare the output of your solution and the naive one. It's quite likely that you'll a test case your code fails if it's actually wrong (that's exactly how I found a counterexample to your algorithm).