【LeetCode-数组】最大子序和

题目描述

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

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

题目链接： https://leetcode-cn.com/problems/maximum-subarray/

思路1

动态规划。

• 记录当前子序列的和curSum;
• 如果curSum>0，说明curSum对接下来的结果有增益效果，则curSum加上下一个数字；
• 如果curSum<=0，则说明curSum对不会使接下来的结果变大，所以丢弃curSum，从下一个数字重新开始计算curSum;
• 比较curSum与当前子序列和的最大值maxSum，将两者之中的较大者赋给maxSum.
  代码如下：

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if(nums.empty()){
            return 0;
        }
        if(nums.size()==1){
            return nums[0];
        }

        int curSum = 0;
        int maxSum = 0x80000000; // 不能初始化为 0
        for(int i=0; i<nums.size(); i++){
            if(curSum<=0){
                curSum = nums[i];
            }else{
                curSum+=nums[i];
            }
            maxSum = max(curSum, maxSum);
        }
        return maxSum;
    }
};

• 时间复杂度：O(n)
  因为只遍历一遍数组，所以时间复杂度为O(n).
• 空间复杂度：O(1)

还可以直接使用dp数组来写，使用dp[i]表示以第i个数结尾的最长子序列和。分析过程如下：

• n=0，dp[0]=nums[0];
• n=1, 表示数组中有两个数，因为使用dp[i]表示以第i个数结尾的最长子序列和，所以dp[1]=max(dp[0]+nums[1], nums[1]);
• 以此类推，得到dp[i]=max(dp[i-1]+nums[i], nums[i]).

代码如下：

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if(nums.empty()) return 0;

        int dp[nums.size()];
        memset(dp, 0, sizeof(dp));
        dp[0] = nums[0];
        int maxSum = dp[0];
        for(int i=1; i<nums.size(); i++){
            dp[i] = max(dp[i-1]+nums[i], nums[i]);
            maxSum = max(dp[i], maxSum);
        }
        return maxSum;
    }
};

技巧

可以将0x80000000（int最小值）赋值给max用来记录最大值，0x7fffffff(int最大值)赋值给min用来记录最小值。