Leetcode-53. 最大子序和

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;
    }
}