53 最大子数组和

https://leetcode.cn/leetbook/read/top-interview-questions-easy/xn8fsh/

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/description/

cost: 8m9s

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        vector<int> memo(nums.size());
        memo[0] = nums[0];
        int maxSum = memo[0];
        for (int i = 1; i < nums.size(); i++) {
            memo[i] = memo[i - 1] > 0 ? memo[i - 1] + nums[i] : nums[i];
            if (maxSum < memo[i]) {
                maxSum = memo[i];
            }
        }
        return maxSum;
    }
};

• 时间复杂度：O(n)
• 空间复杂度：O(n)