力扣121. 买卖股票的最佳时机（后缀后）

Problem: 121. 买卖股票的最佳时机

题目描述

思路及解法

在本题中我们为避免暴力双循环可以采取后缀和的方式，具体的：

1.统计后缀后：在定义一个和prices等大的数组max用于记录后缀和，然后循环从prices数组后开始遍历，如果当prices[i]大于max[i]，则更新当前max[i]处的值为prices[i],否则max[i]还是为上一阶段的最大值；
2.找出最大差值：定义一个用于记录差值的int变量result，同时正向遍历prices若max[i] - prices[i] > result则更新result为max[i] - prices[i]

复杂度

时间复杂度:

$O(n)$；其中$n$为数组prices的大小

空间复杂度:

$O(n)$

Code

class Solution {
   
public:
    /**
     * Suffix sum
     * @param prices
     * @return int
     */
    int maxProfit(vector<int> &prices) {
   
        int n = prices.size();
        vector<int> max(n);
        int curMax = 0;
        //Statistical suffix sum
        for (int i = n - 1; i >= 0; --i) {
   
            max[i] = curMax;
            if (prices[i] > curMax) {
   
                curMax = prices[i];
            }
        }
        int result = 0;
        for (int i = 0; i < n; ++i) {
   
            if (max[i] - prices[i] > result) {
   
                result = max[i] - prices[i];
            }
        }
        return result;
    }
};