题解 | #买卖股票的最好时机(三)#
买卖股票的最好时机(三)
https://www.nowcoder.com/practice/4892d3ff304a4880b7a89ba01f48daf9
提供一个非 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; } };