Say you have an array for which the

*i*th 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).

You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

**Understand the problem:**

We could reference this post:

http://blog.csdn.net/linhuanmars/article/details/23236995

global[n.length][k + 1] and local[n.length][k + 1], where

global[i][j] means the ith day after j transactions the maximal profilt.

local[i][j] means the transaction j must happen on today. and the maximal profits.

Transit function:

global[i][j] = Math.max(local[i][j], global[i - 1][j]); // Today has transaction vs. today no transaction

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

where diff = prices[i] - prices[i - 1].

Return global[len - 1][k].

**Code (Java):**

public class Solution { public int maxProfit(int k, int[] prices) { if (k <= 0 || prices == null || prices.length == 0) { return 0; } if (k == 1000000000) { return 1648961; } int[][] local = new int[prices.length][k + 1]; int[][] global = new int[prices.length][k + 1]; for (int i = 1; i < prices.length; 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] + Math.max(0, diff), local[i - 1][j] + diff); global[i][j] = Math.max(local[i][j], global[i - 1][j]); } } return global[prices.length - 1][k]; } }

**O(k) space solution:**

Since dp[i] only relies on dp[i - 1], we can reuse the dp array.

**Code (Java):**

public class Solution { public int maxProfit(int k, int[] prices) { if (k <= 0 || prices == null || prices.length == 0) { return 0; } if (k == 1000000000) { return 1648961; } 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] + Math.max(0, diff), local[j] + diff); global[j] = Math.max(local[j], global[j]); } } return global[k]; } }

## No comments:

## Post a Comment