首页 > 代码库 > Best Time to Buy and Sell Stock IV 解答
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.
For example, given prices = [4,4,6,1,1,4,2,5], and k = 2, return 6.
Answer
用DP解答。
local[i][j] 表示0～i的数，最多j次交易，并且最后一次交易必须包含prices[j]（即最后一天必须卖出），收益最大值。
global[i][j] 表示0~i的数，最多j次交易，收益最大值。
diff = prices[i] - prices[i-1]
local[i][j] = max(global[i-1][j-1] + max(diff,0), local[i-1][j]+diff)
global[i][j] = max(local[i][j], global[i-1][j])
local[i-1][j] + diff 表示第i-1天，买进prices[i-1]，第i天卖出。由于local[i-1][j]表示最后一次交易必须包含prices[i-1]，即prices[i-1]必须卖出。所以可以把第i-1天的交易和第i天的交易合并，即成了最多j次交易，最后一天交易必须卖出prices[i]。
global[i-1][j-1] 表示前i-1天，最多j-1次交易。最后一天比较diff，如果diff>0，则第i-1天买进，第i天卖出；如果diff<0，则第i天买进，第i天卖出。
class Solution {
/**
* @param k: An integer
* @param prices: Given an integer array
* @return: Maximum profit
*/
public int maxProfit(int k, int[] prices) {
// write your code here
if (prices == null || prices.length == 0 || k == 0) {
return 0;
}
int len = prices.length;
if (k >= len / 2) {
int profit = 0;
for (int i = 1; i < len; i++) {
if (prices[i] > prices[i - 1]) {
profit += (prices[i] - prices[i - 1]);
}
}
return profit;
}
int[][] local = new int[len][k + 1];
int[][] global = new int[len][k + 1];
for (int i = 0; i < len; i++) {
local[i][0] = 0;
global[i][0] = 0;
}
Arrays.fill(local[0], 0);
Arrays.fill(global[0], 0);
for (int i = 1; i < len; i++) {
for (int j = 1; j <= k; j++) {
int diff = prices[i] - prices[i - 1];
local[i][j] = Math.max(local[i - 1][j] + diff,
global[i - 1][j - 1] + Math.max(diff, 0));
global[i][j] = Math.max(local[i][j], global[i - 1][j]);
}
}
return global[len - 1][k];
}
};
Best Time to Buy and Sell Stock IV 解答
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。