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).
思路：
自己没有想出来解法，参见了其他人的解法。
动态规划，局部最优与全局最优。
我们需要维护如下两个量：
global[i][j]:当前到达第i天最多可以进行j次交易，所得到的最大利润。
local[i][j]:当前到达第i天最多可以进行j次交易，而且最后一次交易在当天卖出，所得到的最大利润。
状态转移方程：
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)
上述方程比较两个量的大小：
①全局到i-1天进行j-1次交易，然后加上今天的交易（如果今天的交易赚钱的话）。
②取局部第i-1天进行j次交易，然后加上今天的差值（local[i-1][j]是第i-1天卖出的交易，它加上diff后变成第i天卖出，并不会增加交易次数。无论diff是正还是负都要加上，否则就不满足local[i][j]必须在最后一天卖出的条件了）
另外需要注意的一个问题是，当k远大于数组的大小时，上述算法将变得低效。因此将其改用不限交易次数的方式解决。
public int maxProfit(int k, int[] prices) {
int res = 0;
if (k < 1 || prices == null || prices.length < 2) {
return res;
}
if (k >= prices.length / 2) return quickSolve(prices);
int[] local = new int[k + 1];
int[] global = new int[k + 1];
for (int i = 0; i < prices.length - 1; i++)
{
int diff = prices[i+1]-prices[i];
for(int j = k; j >= 1; j--)
{
local[j] = Math.max(global[j-1]+(diff>0?diff:0), local[j]+diff);
global[j] = Math.max(local[j],global[j]);
}
}
return global[k];
}
private int quickSolve(int[] prices) {
int len = prices.length, profit = 0;
for (int i = 1; i < len; i++)
// as long as there is a price gap, we gain a profit.
if (prices[i] > prices[i - 1]) profit += prices[i] - prices[i - 1];
return profit;
}
下面这种思路更好理解一些：
public int maxProfit1(int k, int[] prices) {
int n = prices.length;
if (n <= 1)
return 0;
//if k >= n/2, then you can make maximum number of transactions.
if (k >= n/2) {
int maxPro = 0;
for (int i = 1; i < n; i++) {
if (prices[i] > prices[i-1])
maxPro += prices[i] - prices[i-1];
}
return maxPro;
}
int[][] dp = new int[k+1][n];
for (int i = 1; i <= k; i++) {
int localMax = dp[i-1][0] - prices[0];
for (int j = 1; j < n; j++) {
dp[i][j] = Math.max(dp[i][j-1], prices[j] + localMax);
localMax = Math.max(localMax, dp[i-1][j] - prices[j]);
}
}
return dp[k][n-1];
}