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 = [0]
输出:0
示例 4:

输入:nums = [-1]
输出:-1
示例 5:

输入:nums = [-100000]
输出:-100000
解题思路
dp[i]:表示到i的最大子序和,如果到前一个元素的最大子序和大于0,则保留,否则舍弃
//动态规划的优化:dp[i]表示到i的最大子序和
//如果sum大于0则保留,否则舍弃重新开始---利用一个变量求保存最大
//由于dp[i]之和dp[i-1]有关,所以可以只保存dp[i-1];
图片说明

class Solution {
    public int maxSubArray1(int[] nums) {
        //动态规划的优化:dp[i]表示到i的最大子序和
        //如果sum大于0则保留,否则舍弃重新开始---利用一个变量求保存最大
        //由于dp[i]之和dp[i-1]有关,所以可以只保存dp[i-1];
        int ans = nums[0];
        int sum = 0;
        for(int num: nums) {
            if(sum > 0) {
                sum += num;
            } else {
                sum = num;
            }
            ans = Math.max(ans, sum);
        }
        return ans;
    }
    public int maxSubArray(int[] nums) {
        int ans = nums[0];
        int n=nums.length;
        int[] dp=new int[n];
        dp[0]=nums[0];
        for(int i=1;i<n;i++) {
            if(dp[i-1] > 0) {
                dp[i]=dp[i-1]+nums[i];
            } else {
                dp[i]=nums[i];
            }
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }
}