Leetcode discuss: 123. Best Time to Buy and Sell Stock III

Here is the link. 

C# - dynamic programming - case study - choose DP first always

Jan. 6, 2020

This solution is based on the Best Time to Buy and Sell Stock (Easy level) where you track the global minimum price and maximum profit. At most two trades are considered, so the important task is to divide the array into two areas.

Go left to right, and store the best profit for each day individually in left.
left[i] shows the max profit for days [1, i]

Go right to left, store best profit in right
right[i] shows the max profit for days [i + 1, n]

The maximum profit is the maximum of left[i] + right[i] for i = 0 to n - 1.

Case study
Input: prices = [3,3,5,0,0,3,1,4]
Output: 6

The idea is to find at most two trades to make maximum profit. The array interval can be divided into two intervals. There are at most n ways to divide.

It is to think about dynamic programming way to use exisitng calculated solution.
[3, 3, 5], how to calculate the maximum profit for one trade in the interval, last index is 2, value 5, only need to find minimum value in previous interval.
left[2] = Math.Max(left[1], 5 - minPrice[i - 1]).

Just consider current price 5 to calculate it's maximum profit value.

[0,0,3,1,4]
this one is to work from right to left iteration order. Index position is 4, value 0, the maximum profit to purchast at index = 4 is to find maximum profit in right side of the index = 4.

public class Solution {
    // at most two trades - maximum profit
        // dynamic programming solution
        // 
        public int MaxProfit(int[] prices) 
        {
            var n = prices.Length;

            var minLeft = Int32.MaxValue;
            var maxRight = 0;
            var maxProfit = 0;

            var left  = new int[n + 1]; 
            var right = new int[n + 1];

            // interval from [0, i]
            for (int i = 0; i < n; ++i) 
            {
                var price  = prices[i];                

                minLeft     = Math.Min(minLeft, price);                
                left[i + 1] = Math.Max(left[i], price - minLeft);                
            }

            // interval from [n - i - 1, n)
            for (int i = 0; i < n; ++i)
            {                
                var price = prices[n - i - 1];
                
                maxRight = Math.Max(maxRight, price);               
                right[n - i - 1] = Math.Max(right[n - i], maxRight - price);
            }

            // at most two trades
            for (int i = 0; i < n; i++ )
            {
                maxProfit = Math.Max(maxProfit, left[i] + right[i]);
            }
            
            return maxProfit;            
        }
}