# [leetcode] Best Time to Buy and Sell Stock IV 1

### 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).

Credits:
Special thanks to @Freezen for adding this problem and creating all test cases.

tag: dynamic programming

global[i][j]表示到第i天时，完成j次交易所能达成的最大利润。

local[i][j]表示到第i天时，完成j次交易，且第j次交易在第i天卖出所能达成的最大利润。

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

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

global[i – 1][j – 1] + max(diff, 0)：i-1天完成j-1次交易，第j次交易在第i天当天买卖（0）或者第i-1天买，第i天卖（diff）的最大值。

local[i-1][j] + diff：i-1天完成j次交易且第j次交易在i-1天卖出，再在第i-1天买入，在第i天卖出的最大值。（这样第j次交易连起来了，还是j次交易）

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

This site uses Akismet to reduce spam. Learn how your comment data is processed.