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

 Here is the link. 

C# - mock interview - performance - design issue

Jan. 6, 2020
It is challenge for me to analyze this written solution in mock onsite interview, how to quickly modify the design to make it work, fix TLE error.

The TLE problem
The function I designed called MaxProfitOneTrade takes O(N) time for each start variable.
It should be simplifyed using dynamic programming to make it O(1).

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace stockTradeII
{
    class Program
    {
        static void Main(string[] args)
        {
            var result = MaxProfit(new int[]{1, 2});
        }

        public static int MaxProfit(int[] prices)
        {
            if (prices == null || prices.Length < 4)
            {
                return 0;
            }

            var length = prices.Length;
            var twoOrderProfit = 0;

            // at most 2 
            for (int i = 0; i + 1 < length; i++)
            {
                var first = MaxProfitOneTrade(prices, 0, i);
                var second = MaxProfitOneTrade(prices, i, length - i);
                var current = first + second;
                twoOrderProfit = current > twoOrderProfit ? current : twoOrderProfit;
            }

            return twoOrderProfit;
        }

        /// <summary>
        /// the problem of the design is time complexity
        /// O(N), it can be O(1), using extra space, save all profit for each position
        /// </summary>
        /// <param name="prices"></param>
        /// <param name="start"></param>
        /// <param name="length"></param>
        /// <returns></returns>
        private static int MaxProfitOneTrade(int[] prices, int start, int length)
        {
            if (prices == null || length == 0)
            {
                return 0;
            }

            var minPrice = prices[start];
            var maxProfit = 0;

            for (int i = start + 1; i < start + length; i++)
            {
                var current = prices[i];
                var isSmaller = current < minPrice;
                if (isSmaller)
                {
                    minPrice = current;
                }
                else
                {
                    var profit = current - minPrice;
                    maxProfit = profit > maxProfit ? profit : maxProfit;
                }
            }

            return maxProfit;
        }
    }
}