Leetcode 123 - buy and sell stock - pass online judge - study code using dynamic programming

Leetcode123_BuyAndSellStock.cs

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

namespace Leetcode123_buyAndSellStock
{
    /// <summary>
    /// Leetcode 123: 
    /// https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/#/description
    /// 
    /// Hard level algorithm
    /// 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 (ie, you must sell the stock before you buy again).
    /// </summary>
    class Program
    {
        static void Main(string[] args)
        {
            RunTestcase(); 
        }
        
        /// <summary>
        /// Fail test case [1,2,4,2,5,7,2,4,9,0]. It should be 13, but my result is 12
        /// 
        /// buy at 1 sell at 7, buy at 2 and sell at 9
        /// </summary>
        public static void RunTestcase()
        {
            var testcase = new int[] { 1, 2, 4, 2, 5, 7, 2, 4, 9, 0 };
            var result = MaxProfit(testcase); 
        }

        // f[k, index] represents the max profit up until prices[index] 
        // (Note: NOT ending with prices[index]) using at most k transactions. 
        //
        // Subproblem approach: 
        // problem 1: f[k, index - 1] - the max profit up until prices[index - 1]
        // problem 2: prices[index] is involved, that is time to sell the stock, 
        // and the time to purchse the stock can be any one from [0, index - 1]. 
        // we need to choose the maximum one from those index number of choices. 
        // 
        // Let us work on the recurrence formula:
        // f[k, index] = max(f[k, index - 1], prices[index] - prices[j] + f[k - 1, j]) 
        // { j in range of [0, index  - 1] }; 
        // in other words, put maximum calculation inside the first maximum function. 
        // f[k, index] = max(f[k, index - 1], prices[index] + max(f[k - 1, j] - prices[j]))
        // 
        // Base cases:
        // f[0, index] = 0; 0 times transation makes 0 profit
        // f[k, 0] = 0; if there is only one price data point you can't make any money 
        // no matter how many times you can trade
        public static int MaxProfit(int[] prices)
        {                        
            if (prices.Length <= 1)
            {
                return 0;
            }
            
            int K = 2; // number of max transation allowed
            int maxProfit = 0;

            int length = prices.Length; 

            var profit = new int[K+1][]; 
            for(int i = 0; i < K + 1; i++)
            {
                profit[i] = new int[length];                 
            }
            
            for (int i = 1; i < K + 1; i++) { // at most K =2 transaction, i is number of transaction
                int maximum = profit[i - 1][0] - prices[0];  // maximum value for all possible purchase time
                for (int j = 1; j < prices.Length; j++) {    // j - time stamp
                    // maximum subproblem
                    var lastPurchaseTime = j;
                    var current = profit[i - 1][lastPurchaseTime] - prices[lastPurchaseTime];
                    maximum = Math.Max(maximum, current);

                    // recurrence formula 
                    profit[i][j] = Math.Max(profit[i][j - 1], prices[j] + maximum);                    

                    maxProfit = Math.Max(profit[i][j], maxProfit);
                }
            }

            return maxProfit;                      
        }      
    }
}