[LeetCode] Best Time to Buy and Sell Stock III

Problem: Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

Approach: Use DP.

Implementation in C#:

        public int MaxProfitWith2Transaction(int[] prices)

        {

            if (prices == null || prices.Length <= 1)

            {

                return 0;

            }

            int[] profit = new int[prices.Length];

            int maxPrice = prices[prices.Length - 1];

            for (int i = prices.Length - 2; i >= 0; --i)

            {

                if (maxPrice < prices[i])

                {

                    maxPrice = prices[i];

                }

                profit[i] = Math.Max(profit[i + 1], maxPrice - prices[i]);

            }

            int minPrice = prices[0];

            for (int i = 1; i < prices.Length; ++i)

            {

                if (minPrice > prices[i])

                {

                    minPrice = prices[i];

                }

                profit[i] = Math.Max(profit[i - 1], profit[i] + (prices[i] - minPrice));

            }

            return profit[profit.Length - 1];

        }

Complexity: O(n)