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

题目描述

思路

1.定义一个int数组max大小同prices；定义int变量curMax初始化为0；
2.从后往前遍历数组，若当前元素prices[i] > curMax时，则使将其赋值给curMax再将curMax填写到max[i];
3.定义int变量result再从前往后遍历，若price[i] - max[i] > result,则更新result，最后返回result。

复杂度

时间复杂度:

$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;
    }
};