February 13, 2022 - Maximum subarray and

Give you an array of integers nums , Please find a continuous subarray with the largest sum （ A subarray contains at least one element ）, Return to its maximum and .

Subarray Is a continuous part of the array .

Example 1：

Input ：nums = [-2,1,-3,4,-1,2,1,-5,4]
Output ：6
explain ： Continuous subarray [4,-1,2,1] And the biggest , by 6 .
Example 2：

Input ：nums = [1]
Output ：1
Example 3：

Input ：nums = [5,4,-1,7,8]
Output ：23

Tips ：

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4

java Code ：

class Solution {
    public int maxSubArray(int[] nums) {
//        int pre = 0, maxAns = nums[0];
//        for (int x : nums) {
//            pre = Math.max(pre + x, x);
//            maxAns = Math.max(maxAns, pre);
//        }
//        return maxAns;
        
        // Dynamic programming , Record dp[i] Record from 0 To i The largest substring of 
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int maxAns = nums[0];
        
        for(int i=1;i<nums.length;i++) {
            dp [i] = Math.max(nums[i], dp[i-1]+nums[i]);
            maxAns = Math.max(maxAns, dp[i]);
        }
        
        return maxAns;
    }
}