53. 最大子数组和

题目链接

解题思路

• 最大子数组问题，有两个基本的想法，以i开头的子数组结果是怎样的，求出所有的结果，最优的那个，就是答案；以i结尾的子数组结果是怎样的，求出所有的结果，最优的那个，就是答案。
• 本题我们可以考虑，「以i结尾的结果是怎样的」，为啥？因为我们要求的是最大的累加和，我们求出了res1=「以i结尾的结果」，求i+1的结果就很方便了，如果res1为正数，则i+1的结果就是res1 + nums[i + 1]，如果res1为负数，则i+1的结果就是nums[i + 1]

代码

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        int pre = nums[0];   // 0结尾的结果
        int ans = pre;
        for (int i = 1; i < n; ++i) {   // 我们现在求以i结尾的结果是多少
            if (pre > 0) {    // 如果前面的累加和大于0   则加上
                pre += nums[i];
            } else {    // 否则不加
                pre = nums[i];
            }
            ans = max(ans, pre);     // 更新结果
        }
        return ans;
    }
};