地址

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/

题目

Say you have an array for which the i-th 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.

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

Example 1:

Input: [2,4,1], k = 2
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.

Example 2:

Input: [3,2,6,5,0,3], k = 2
Output: 7
Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4.
             Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.

思路

dpi表示：以i结尾时，进行了j次交易时的利润。（这里我把买入和卖出分别算一次交易，所以j为奇数时表示已买入一个股票 ，j为偶数时表示之前购买的股票全部卖出了）。

j==1: dpi=max{dpi-1, dpi-1-prices[i], -prices[i]}, 0<i;

j==0:dpi=max{dpi-1, dpi-1+prices[i]}, i>0;

代码里用了滚动数组。

代码

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int dp[2][100000];
        int n = prices.size();
        int ans = 0;
        memset(dp, 0, sizeof dp);
        k=min(n,k*2);
        int now=0;
        for(int i=0;i<n;++i,now^=1)
        {
            for(int j=1;j<=k;++j)
            if(j&1)
            {
                dp[now][j] = -prices[i];
                if(i>0)
                    dp[now][j] = max(dp[now][j], max(dp[now^1][j], dp[now^1][j-1]-prices[i]));
            }
            else
            {
                if(i>0)
                    dp[now][j] = max(dp[now][j], max(dp[now^1][j],dp[now^1][j-1]+prices[i]));

            }
            
            //for(int j=1;j<=k;++j)
            //    printf("%d%c",dp[i][j],j==k?'\n':' ');
        }
        for(int i=2;i<=k&&n>1;i+=2)
            ans=max(ans, dp[now^1][i]);
        return ans;
    }
};