leetcode筆記：Best Time to Buy and Sell Stock IV

leetcode筆記：Best Time to Buy and Sell Stock IV

一. 題目描述

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.

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

二. 題目分析

這一題的難度要遠高於前面幾題，需要用到動態規劃，代碼參考了博客：http://www.cnblogs.com/grandyang/p/4295761.html

這裡需要兩個遞推公式來分別更新兩個變量local和global，然後求至少k次交易的最大利潤。我們定義local[i][j]為在到達第i天時最多可進行j次交易並且最後一次交易在最後一天賣出的最大利潤，此為局部最優。然後我們定義global[i][j]為在到達第i天時最多可進行j次交易的最大利潤，此為全局最優。它們的遞推式為：

local[i][j] = max(global[i - 1][j - 1] + max(diff, 0), local[i - 1][j] + diff)

global[i][j] = max(local[i][j], global[i - 1][j])

三. 示例代碼

#include 
#include 
#include 
#include 
#include 
using namespace std;

class Solution {
public:
    int maxProfit(int k, vector &prices) {
        if(prices.empty() || k == 0)
          return 0;

        if(k >= prices.size())
          return solveMaxProfit(prices);

        vector global(k + 1, 0);
        vector local(k + 1, 0);

        for(int i = 1; i < prices.size(); i++) {
            int diff = prices[i] - prices[i - 1];
            for(int j = k; j >= 1; j--) {
                local[j] = max(local[j] + diff, global[j - 1] + max(diff, 0));
                global[j] = max(global[j], local[j]);
            }
        }

        return global[k];
    }

private:
    int solveMaxProfit(vector &prices) {
        int res = 0;
        for(int i = 1; i < prices.size(); i++) {
            int diff = prices[i] - prices[i - 1];
            if(diff > 0)
              res += diff;
        }
        return res;
    }
};