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
ここでは、2つの変数localおよびglobalをそれぞれ更新し、その後、少なくともk回の取引の最大利益を求める2つの繰返し式が必要である.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 <vector>
#include <iostream>
#include <cstdio>
#include <climits>
#include <cmath>
using namespace std;

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

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

        vector<int> global(k + 1, 0);
        vector<int> 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<int> &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;
    }
};

四.小結
参照リンク:http://www.cnblogs.com/grandyang/p/4295761.html