题解 | #买卖股票的最好时机(三)#

提供一个非 dp 的思路，但是要遍历两边数组。

第一次遍历，对于每个位置 i，求左边一次交易的最大值，右边一次交易的最大值。

第二次遍历最大值数组，对每个位置 i 求左右两个最大值的和。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 两次交易所能获得的最大收益
     * @param prices int整型vector 股票每一天的价格
     * @return int整型
     */
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (n <= 1) {
            return 0;
        }
        vector<int> left_max(n, 0), right_max(n, 0);
        int lmax = prices[0], lmin = prices[0];
        int rmax = prices[n - 1], rmin = prices[n - 1];
        for (int i = 1; i < n - 1; ++i) {
            // left
            left_max[i] = left_max[i - 1];
            if (prices[i] > lmax) {
                lmax = prices[i];
                if (lmax - lmin > left_max[i]) {
                    left_max[i] = lmax - lmin;
                }
            } else if (prices[i] < lmin) {
                lmin = prices[i];
                lmax = prices[i];
            }
            // right
            right_max[n - 1 - i] = right_max[n - 1 - i + 1];
            if (prices[n - 1 - i] < rmin) {
                rmin = prices[n - 1 - i];
                if (rmax - rmin > right_max[i]) {
                    right_max[n - 1 - i] = rmax - rmin;
                }
            } else if (prices[n - 1 - i] > rmax) {
                rmax = prices[n - 1 - i];
                rmin = rmax;
            }
            // cout << left_max[i] << right_max[n - 1 - i] << endl;
        }
        // left
        left_max[n - 1] = left_max[n - 2];
        if (prices[n - 1] > lmax) {
            lmax = prices[n - 1];
            if (lmax - lmin > left_max[n - 1]) {
                left_max[n - 1] = lmax - lmin;
            }
        }
        // right
        right_max[0] = right_max[1];
        if (prices[0] < rmin) {
            rmin = prices[0];
            if (rmax - rmin > right_max[0]) {
                right_max[0] = rmax - rmin;
            }
        }
        int res = 0;
        for (int i = 0; i < n; ++i) {
            if (left_max[i] + right_max[i] > res) {
                res = left_max[i] + right_max[i];
            }
        }
        return res;
    }
};