Greedy - 53. Maximum subarray sum

1 Title Description

53. 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 .

2 Title Example

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

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/maximum-subarray

3 Topic tips

1 <= nums.length <= 10⁵
-10⁴ <= nums[i] <= 10⁴

4 Ideas

Where is greedy ?
If -2 1 together , When calculating the starting point , It must be from 1 Start calculating , Because negative numbers only lower the sum , This is the place of greed !
Local optimum : At present “ Continuous and " Give up immediately when it's negative , Recalculate from the next element " Continuous and ", Because negative numbers plus the next element “ Continuous and " It's just getting smaller .
The best in the world : Select the maximum " Continuous and ”
In the case of local optimization , And record the maximum “ Continuous and ”, We can deduce the global optimal .
From a code perspective : Traverse nums, Start from scratch count The cumulative , If count Once you add nums[i] It becomes negative , Then we should start from nums[i+1] Start from 0 The cumulative count 了 , Because it has become negative count, It will only drag down the total .
This is equivalent to continuously adjusting the starting position of the maximum suborder and interval in the violent solution .
Then some students asked , There is no need to adjust the end position of the interval ? How to get the maximum " Continuous and " Well ?
The end position of the interval , In fact, if count Got the maximum value , Recorded in time . For example, the following code :

if (count > result) result = count;

This is equivalent to using result Record the maximum suborder and interval sum ( In disguise, the end position is adjusted ).

The starting position of red is greedy. Every time you take count When it's positive , Start the statistics of an interval .

Time complexity :O(n)· Spatial complexity :O(1)
Of course, the title doesn't say if the array is empty , What should be returned , So if the array is empty, everything can be returned .
Many students think that if the input use cases are -1, Or all negative numbers , The result of this greedy algorithm is 0, This is another classic case that proves that brain hole simulation is unreliable , I suggest you run the code and try , You know the , Will also understand why result To initialize to the minimum negative number .

5 My answer

class Solution {
    
    public int maxSubArray(int[] nums) {
    
        if (nums.length == 1){
    
            return nums[0];
        }
        int sum = Integer.MIN_VALUE;
        int count = 0;
        for (int i = 0; i < nums.length; i++){
    
            count += nums[i];
            sum = Math.max(sum, count); //  Take the maximum value of interval accumulation （ It is equivalent to continuously determining the termination position of the maximum subsequence ）
            if (count <= 0){
    
                count = 0; //  It is equivalent to resetting the starting position of the maximum sub order , Because when you encounter a negative number, you must pull down the sum 
            }
        }
       return sum;
    }
}