【leetcode】188. Best Time to Buy and Sell Stock IV

Difficulty:Hard

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 k transactions.

解題思路：

這道題目首先可以分成兩種情況：

1.對于k>=n的情況，也就是可以交易的次數已經大于總的天數，其實相當于在n天之内進行無限次交易，這樣将問題轉化為了Best Time to Buy and Sell Stock II類型的問題，是以不再進行贅述。

2.當k<n的情況，就需要用到動态規劃的思想了：将整個問題劃分為局部最優解和全局最優解，并且分别設立兩個大小為N的數組，l[n]和g[n]，用來存儲交易i次時的局部最優解和全局最優解：

對于局部最優的情況： 要求在第i天一定要完成賣出的交易。

對于全局最優解的情況：第i天可以交易也可以不交易。

是以需要對兩個數組應用狀态傳遞方程。

局部最優解情況下交易j次的最大值應該等于交易j次的局部最優解加上當天nums[i]-nums[i-1]的值與交易j-1次的全局最優解+當天收益

而全局最優解更新應該為交易j次情況下當天的全局最優解與局部最優解的最大值。最終傳回代表交易k次的全局最優解即可

代碼如下：

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n=prices.size();
        if(n<2) return 0;
        if(k>=n) return other(prices);
        int l[n+1]={0};
        int g[n+1]={0};
        for(int i=1;i<n;i++)
        {
            int sub=prices[i]-prices[i-1];
            for(int j=k;j>=1;j--)
            {
                int temp1=0;
                temp1=sub;
                temp1=temp1+g[j-1];
                if(temp1>l[j]+sub) l[j]=temp1;
                else l[j]=l[j]+sub;
                if(l[j]>g[j]) g[j]=l[j];
            }
        }
        int ans=g[k];
        return ans;
        
    }
    int other(vector<int>& prices) {
        int ans=0;
        int n=prices.size();
        if(n<2) return 0;
        for(int i=0;i<n-1;i++)
        {
            if(prices[i]<prices[i+1]) ans+=prices[i+1]-prices[i];
        }
        return ans;
    }
};