Say you have an array for which theithelement is the price of a given stock on dayi.
Design an algorithm to find the maximum profit. You may complete at mostktransactions.
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
Example 1:
Input: [2,4,1], k = 2
Output: 2
Explanation:
Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.
Example 2:
Input: [3,2,6,5,0,3], k = 2
Output: 7
Explanation:
Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4.
Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
2. Implementation
(1) DP
class Solution {
public int maxProfit(int k, int[] prices) {
if (prices == null || prices.length == 0) {
return 0;
}
if (k >= prices.length / 2) {
return maxProfitWithUnlimitedTransactions(prices);
}
int[][] dp = new int[k + 1][prices.length];
for (int i = 1; i <= k; i++) {
int holding = -prices[0];
for (int j = 1; j < prices.length; j++) {
dp[i][j] = Math.max(dp[i][j - 1], holding + prices[j]);
holding = Math.max(holding, dp[i - 1][j - 1] - prices[j]);
}
}
return dp[k][prices.length - 1];
}
public int maxProfitWithUnlimitedTransactions(int[] prices) {
int curMax = 0;
int max = 0;
for (int i = 1; i < prices.length; i++) {
curMax = prices[i] > prices[i - 1] ? curMax + prices[i] - prices[i - 1] : curMax;
max = Math.max(max, curMax);
}
return max;
}
}