LeetCode 题解（82）: 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.
【LeetCode 题解（82）: Best Time to Buy and Sell Stock IV】Design an algorithm to find the maximum profit. You may complete at mostk transactions.
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
题解：
需要用两个表来记录：a) 在i天内（包括i）进行至多j次交易的最大获利，用global[i][j]表示，及 b) 第i天卖出股票，完成至多j次交易的最大获利，用local[i][j]表示。
那么递推关系式为：
local[0][j] = global[0][j] = 0, for j = 0,...,k

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

其中： global[i-1][j-1] + prices[i]-prices[i-1] 表示：前i-1天完成了j-1笔交易的最大获利，加上，第i-1天买入并在第i天卖入的收入
local[i-1][j] + prices[i] - prices[i-1] 表示：前i-1已经完成了j笔交易，并且最后一次卖出是在第i-1天发生呢，那么我们把卖出时间推迟一天（由i-1推迟到i），则仍是j笔交易，但是利润变化为prices[i] - prices[i-1]，所以我们还要加上这一部分。
global的递推比较好理解：要么在i-1天完成j笔交易，要么第i天完成第j笔交易。

c++版：

class Solution { public: int maxProfit(int k, vector &prices) { if(k > prices.size()) { int profit = 0; for(int i = 1; i < prices.size(); i++) if(prices[i] > prices[i-1]) profit += prices[i] - prices[i-1]; return profit; }vector local(k+1, 0); vector global(k+1, 0); for(int i = 1; i < prices.size(); i++) { for(int j = 1; j <= k; j++) { local[j] = max(global[j-1] + max(prices[i] - prices[i-1], 0), local[j] + prices[i] - prices[i-1]); } for(int j = 1; j <= k; j++) { global[j] = max(global[j], local[j]); } } return global[k]; } };

Java版：

public class Solution { public int maxProfit(int k, int[] prices) { if(k > prices.length) { int gain = 0; for(int i = 1; i < prices.length; i++) if(prices[i] > prices[i-1]) gain += prices[i] - prices[i-1]; return gain; }int[] global = new int[k+1]; int[] local = new int[k+1]; for(int i = 1; i < prices.length; i++) { for(int j = 1; j <= k; j++) { local[j] = Math.max(global[j-1] + prices[i] - prices[i-1], local[j] + prices[i] - prices[i-1]); } for(int j = 1; j <= k; j++) { global[j] = Math.max(global[j], local[j]); } } return global[k]; } }

Python版：

class Solution: # @return an integer as the maximum profit def maxProfit(self, k, prices): if k > len(prices): profit = 0 for i in range(1, len(prices)): if prices[i] > prices[i-1]: profit += prices[i] - prices[i-1] return profitGlobal = [0] * (k+1) Local = [0] * (k+1) for i in range(1, len(prices)): for j in range(1, k+1): Local[j] = max(Global[j-1] + prices[i]-prices[i-1], Local[j] + prices[i] - prices[i-1]) for j in range(1, k+1): Global[j] = max(Global[j], Local[j]) return Global[k]