leetcode-最大子序和

点击：题目链接：给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

思路

由题意可知，若连续的数组内，和的值变小，我们就需要重新开始计数。

所以我们可以推出这样一个递推关系，当第i个元素，当前的它的和的最大值取决于时候前面已知的和加上它是否变小，
若变小，则从当前元素重新计数，即当前的和为f(i) = num[i],
若变大，则当前和为f(i-1)+num[i]

式子可以变为： f(i) = max(num[i], f(i-1)+num[i])

拓展：由于我们只需要f(i-1),为节省空间（不使用哈希表），我们可以利用滚动数组，将f(i-1)表示为一个变量

代码

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int max_val = nums[0];
        int pre_sum = nums[0];

        for(int i=1; i<nums.size(); ++i){
            pre_sum = max(nums[i], (pre_sum+nums[i]));
            max_val = max(pre_sum, max_val);
        }

        return max_val;
    }
};

复杂度

时间：O(N), 空间O(1)