- 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).
- Credits:
- Special thanks to @Freezen for adding this problem and creating all test cases.
123. Best Time to Buy and Sell Stock III 这题是最多能交易 2 次, 而这题是最多 k 次
要用动态规划 Dynamic programming 来解, 需要两个递推公式来分别更新两个变量 local 和 global 定义 local[i][j] 为在到达第 i 天时最多可进行 j 次交易并且最后一次交易在最后一天卖出的最大利润, 此为局部最优然后我们定义 global[i][j] 为在到达第 i 天时最多可进行 j 次交易的最大利润, 此为全局最优它们的递推式为:
- 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])
- C++:
- class Solution {
- public:
- int maxProfit(int k, vector<int> &prices) {
- if (prices.empty()) return 0;
- if (k >= prices.size()) return solveMaxProfit(prices);
- int g[k + 1] = {0};
- int l[k + 1] = {0};
- for (int i = 0; i < prices.size() - 1; ++i) {
- int diff = prices[i + 1] - prices[i];
- for (int j = k; j >= 1; --j) {
- l[j] = max(g[j - 1] + max(diff, 0), l[j] + diff);
- g[j] = max(g[j], l[j]);
- }
- }
- return g[k];
- }
- int solveMaxProfit(vector<int> &prices) {
- int res = 0;
- for (int i = 1; i < prices.size(); ++i) {
- if (prices[i] - prices[i - 1] > 0) {
- res += prices[i] - prices[i - 1];
- }
- }
- return res;
- }
- };
类似题目:
[LeetCode] 121. Best Time to Buy and Sell Stock 买卖股票的最佳时间
[LeetCode] 122. Best Time to Buy and Sell Stock II 买卖股票的最佳时间 II
[LeetCode] 123. Best Time to Buy and Sell Stock III 买卖股票的最佳时间 III
[LeetCode] 309. Best Time to Buy and Sell Stock with Cooldown 买卖股票的最佳时间有冷却期
来源: http://www.bubuko.com/infodetail-2520807.html