**一. 題目描述** 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](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 <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](http://www.cnblogs.com/grandyang/p/4295761.html)