leetcode 123. 买卖股票的最佳时机 III

题目：123. 买卖股票的最佳时机 III - 力扣（LeetCode）

O(N)的算法：

f[i] = max(max(0, prices[i] - min(prices[0], prices[1], ... , prices[i - 1)), f[i - 1]);

g[i] = max(max(0, max(prices[i + 1], prices[i + 2], ... , prices[n - 1])), g[i + 1);

计算最大的 f[i - 1] + g[i] 即可

class Solution {
public:int maxProfit(vector<int>& prices) {int n = (int) prices.size();vector<int> f(n);vector<int> g(n);{int min = prices[0];f[0] = 0;for (int i = 1; i < n; i++) {if (prices[i] < min) min = prices[i];if (prices[i] - min > 0) {f[i] = prices[i] - min;} else {f[i] = 0;}if (f[i - 1] > f[i]) {f[i] = f[i - 1];}}}{int max = prices[n - 1];g[n - 1] = 0;for (int i = n - 2; i >= 0; i--) {if (prices[i] > max) max = prices[i];if (max - prices[i] > 0) {g[i] = max - prices[i];} else {g[i] = 0;}if (g[i + 1] > g[i]) {g[i] = g[i + 1];}}}int t;int ret = g[0];for (int i = 1; i < n; i++) {t = f[i - 1] + g[i];if (t > ret) {ret = t;}}return ret;}
};