188买卖股票的最佳时机4

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

namespace _188BestTimetoBuyandSellStock4
{
    class Program
    {
        static void Main(string[] args)
        {
            //给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
            //设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
            //注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
            //示例 1:
            //输入: [2, 4, 1], k = 2
            //输出: 2
            //解释: 在第 1 天(股票价格 = 2) 的时候买入，在第 2 天(股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4 - 2 = 2 。
            //示例 2:
            //输入: [3, 2, 6, 5, 0, 3], k = 2
            //输出: 7
            //解释: 在第 2 天(股票价格 = 2) 的时候买入，在第 3 天(股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6 - 2 = 4 。
            //随后，在第 5 天(股票价格 = 0) 的时候买入，在第 6 天(股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3 - 0 = 3 。
            int k = 2;
            int[] prices = new int[] { 3, 2, 6, 5, 0, 3 };
            Console.WriteLine(MaxProfit(k,prices));
        }
        //使用DP动态规划求解
        //DP递推公式为：dp[k,i] = max(dp[k,i -1],prices[i] - prices[j] + dp[k-1,j-1]),j = [0,i-1]   
        //dp[k,i]为第i天，最多进行k笔交易的利润，dp[k,i -1]为i的前一天的利润，dp[k-1,j-1]为上一次交易的利润
        //要考虑k过大和prices数组过长，导致内存溢出的情况
        public static int MaxProfit(int k,int[] prices)
        {
            //异常情况处理
            if (k <= 0 || prices.Length <= 1) return 0;
           
            //如果k过大和prices数组过长
            if (k >= prices.Length)
                return _quickSolve(prices);

            int maxProfit = 0;
            int[,] dp = new int[k+1,prices.Length];
            for (int kk = 1; kk <= k; kk++)
            {
                for (int i = 1; i < prices.Length; i++)
                {
                    //cal min
                    int min = prices[0];
                    for (int j = 1; j <= i; j++)
                        min = Math.Min(min, prices[j] - dp[kk - 1,j-1]);
                    dp[kk, i] = Math.Max(dp[kk, i - 1], prices[i] - min);
                }
            }
            maxProfit = dp[k, prices.Length - 1];

            return maxProfit;
        }

        //k过大和prices数组过长
        public static int _quickSolve(int[] prices)
        {
            int maxProfit = 0;
            for (int i = 0; i < prices.Length - 1; i++)
            {
                if (prices[i+1]>prices[i])
                {
                    maxProfit += prices[i + 1] - prices[i];
                }
            }
            return maxProfit;
        }

    }
}