# Best Time to Buy and Sell Stock IV

## Question

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.

Example

Given prices = [4,4,6,1,1,4,2,5], and k = 2, return 6.

## Analysis

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

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

## Solution

Dynamic Programming 2D array implementation

``````class Solution {
/**
* @param k: An integer
* @param prices: Given an integer array
* @return: Maximum profit
*/
public int maxProfit(int k, int[] prices) {
if (prices == null || prices.length < 2) {
return 0;
}
int days = prices.length;

if (days <= k) {
return maxProfit2(prices);
}
// local[i][j] 表示前i天，至多进行j次交易，第i天必须sell的最大获益
int[][] local = new int[days][k + 1];
// global[i][j] 表示前i天，至多进行j次交易，第i天可以不sell的最大获益
int[][] global = new int[days][k + 1];

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

public int maxProfit2(int[] prices) {
int maxProfit = 0;
for (int i = 1; i < prices.length; i++) {
if (prices[i] > prices[i-1]) {
maxProfit += prices[i] - prices[i-1];
}
}
return maxProfit;
}
};
``````

Dynamic Programming 1D array implementation

``````
public class Solution {
public int maxProfit(int k, int[] prices) {
if (prices.length < 2) return 0;
if (k >= prices.length) return maxProfit2(prices);

int[] local = new int[k + 1];
int[] global = new int[k + 1];

for (int i = 1; i < prices.length ; i++) {
int diff = prices[i] - prices[i - 1];

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

return global[k];
}

public int maxProfit2(int[] prices) {
int maxProfit = 0;

for (int i = 1; i < prices.length; i++) {
if (prices[i] > prices[i - 1]) {
maxProfit += prices[i] - prices[i - 1];
}
}

return maxProfit;
}
}
``````