Daily practice (22): maximum sum of continuous subarrays

---

title: Practice every day （22）： The maximum sum of successive subarrays

categories:[ The finger of the sword offer]

tags:[ Practice every day ]

date: 2022/02/21

---

Practice every day （22）： The maximum sum of successive subarrays

Enter an integer array , One or more consecutive integers in an array form a subarray . Find the maximum sum of all subarrays .

The required time complexity is O(n).

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.

Tips ：

1 <= arr.length <= 10^5

-100 <= arr[i] <= 100

source ： Power button （LeetCode）

link ：https://leetcode-cn.com/probl...

Method 1 ： The prefix and

Ideas and algorithms

1. All negative numbers Every time sum Current value , And, in turn, maxsum Compare and take the largest one .
2. Under normal circumstances （ There are positive and negative ） Cumulative prefix and , as long as sum Greater than 0 （ There is also value in existence ）, Just add it up , Judgment is the same as the previous maxsum Who is big , Take the larger value ;
3. Current and smaller to 0 when （ Explain that the negative numbers in the front offset , The following numbers, whether positive or negative , The cumulative sum of the previous 0 It's worthless ）, Then start from the current number again , At the same time, ensure the continuity of subarray .
4. Note that it is not necessary to re assign values when negative numbers are encountered . In addition, we need to constantly judge whether the current sum is the largest .

int maxSubArray(vector<int>& nums) {
    int maxSum = nums[0];    // By default, the first number is the maximum 
    int sum = 0;
    for (int i = 0; i < nums.size(); i++) {                
        sum = sum <= 0 ? nums[i] : sum + nums[i];//  The current sum is not greater than 0 when , Explain that the previous offset , Start over and add up ; Similarly, if they are all negative numbers , Then compare which is the largest , Assign a value to maxSum
        maxSum = sum > maxSum ? sum : maxSum;            //  Keep comparing and updating maxSum
    }
    return maxSum;
}

Method 2 ： Dynamic programming （DP equation ）

Ideas and algorithms

The most primitive dynamic programming

• state :dp[i]: By the end of i The maximum value of the sum at the end of the number
• Transfer : if dp[i - 1] < 0, Then the first is i The maximum value of the sum at the end of the number is i The number itself
• if dp[i - 1] > 0, Then the first is i The maximum value of the sum at the end of the number is dp[i - 1] And dp[i - 1] + nums[i] The larger of the two
• Avoid traversing dp Array , Every comparison dp Compare after the update res And dp[i] As the return value

int maxSubArray(vector<int>& nums) {
    int len = nums.size();
    vector<int> dp(len);
    dp[0] = nums[0];
    int res = nums[0];
    for (int i = 1; i < len; i++) {
        // Judge 
        if(dp[i - 1] > 0) {
            dp[i] = max(dp[i - 1] + nums[i], nums[i]);
        } else {
            dp[i] = nums[i];
        }
        // Ternary operator 
        //dp[i] = (dp[i - 1] > 0) ? dp[i] = max(dp[i - 1] + nums[i], nums[i]) : nums[i];
        res = max(res, dp[i]);
    }
    return res;
}