53. Maximum subarray sum: give you an integer array num, please find a continuous subarray with the maximum sum (the subarray contains at least one element) and return its maximum sum.

Title Description

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 <= 105
-104 <= nums[i] <= 104

Ideas

Using the idea of dynamic programming ：

1. Look directly at the code , The first mock examination clear

Code

class Solution {
    
    public int maxSubArray(int[] nums) {
    
        // initialization 
        //pre It means after adding so far , Maximum value 
        //maxAns Represents the maximum value of continuous addition 
        int pre = 0, maxAns = nums[0];
        // Circular array 
        for(int x : nums){
    
            // Current value , Compare with the result of adding the current value and the previous value 
            pre = Math.max(pre + x, x);
            // Get the maximum value so far 
            maxAns = Math.max(maxAns,pre);
        }
        return maxAns;
    }
}

Code instructions

Note see ...