LeetCode 53:最大子数组和

题目

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。

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

示例 2：
输入：nums = [1]
输出：1

示例 3：
输入：nums = [5,4,-1,7,8]
输出：23

思路

   看到连续子数组，且要求最大和，采用动态规划，首先确定dp[i]含义为包括i及之前的最大连续子数组和，之后确定递推公式，再考虑dp[i]数组初始化，并确定遍历顺序

代码

class Solution {
    public int maxSubArray(int[] nums) {
        int []dp=new int [nums.length];
        int max=-999999;
        dp[0]=nums[0];//dp数组初始化
        for(int i=1;i<nums.length;i++)
        {
           
            dp[i]=Math.max(nums[i],dp[i-1]+nums[i]);//递推公式，从头计算或将当前数加入连续子数组
            
        }
        for(int i=0;i<nums.length;i++)
        if(max<dp[i])//选出最大的dp
        max=dp[i];
        return max;
    }
}

反思

①动态规划按照动归五部曲
②此题也可以使用贪心解法，

   局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。全局最优：选取最大“连续和”

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int result = INT32_MIN;
        int count = 0;
        for (int i = 0; i < nums.size(); i++) {
            count += nums[i];
            if (count > result) { // 取区间累计的最大值（相当于不断确定最大子序终止位置）
                result = count;
            }
            if (count <= 0) count = 0; // 相当于重置最大子序起始位置，因为遇到负数一定是拉低总和
        }
        return result;
    }
};