[LeetCode] Best Time to Buy and Sell Stock III 买股票的最佳时间之三

+关注继续查看

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 two transactions.

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

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])

class Solution {
public:
int maxProfit(vector<int> &prices) {
if (prices.empty()) return 0;
int n = prices.size(), g[n][3] = {0}, l[n][3] = {0};
for (int i = 1; i < prices.size(); ++i) {
int diff = prices[i] - prices[i - 1];
for (int j = 1; j <= 2; ++j) {
l[i][j] = max(g[i - 1][j - 1] + max(diff, 0), l[i - 1][j] + diff);
g[i][j] = max(l[i][j], g[i - 1][j]);
}
}
return g[n - 1][2];
}
};

class Solution {
public:
int maxProfit(vector<int> &prices) {
if (prices.empty()) return 0;
int g[3] = {0};
int l[3] = {0};
for (int i = 0; i < prices.size() - 1; ++i) {
int diff = prices[i + 1] - prices[i];
for (int j = 2; j >= 1; --j) {
l[j] = max(g[j - 1] + max(diff, 0), l[j] + diff);
g[j] = max(l[j], g[j]);
}
}
return g[2];
}
};

本文转自博客园Grandyang的博客，原文链接：买股票的最佳时间之三[LeetCode] Best Time to Buy and Sell Stock III ，如需转载请自行联系原博主。

10091 0
WCF客户端和服务器时间不一致，导致通道建立失败的问题）

772 0

2962 0

1091 0
LeetCode 121 Best Time to Buy and Sell Stock（股票买入卖出的最佳时间）

673 0

13893 0
+关注

2107

1103

《2021云上架构与运维峰会演讲合集》

《零基础CSS入门教程》

《零基础HTML入门教程》