Maximum sum of jz42 continuous subarray (force buckle) (GIF diagram)

Catalog

subject ：

describe

Example 1

Their thinking ：

The illustration ：

---

subject ：

describe

Enter a length of n Integer array array, One or more consecutive integers in an array form a subarray , The minimum length of the subarray is 1. Find the maximum sum of all subarrays .

Data range :

1 <= n <= 2\times10^51<=n<=2×105

-100 <= a[i] <= 100−100<=a[i]<=100

requirement : The time complexity is  O(n)O(n), The space complexity is  O(n)O(n)

Advanced : The time complexity is  O(n)O(n), The space complexity is  O(1)O(1)

Example 1

Input ：

[1,-2,3,10,-4,7,2,-5]

Return value ：

18

explain ：

 It can be seen from the analysis , Subarray of input array [3,10,-4,7,2] The maximum sum can be obtained as 18 

Their thinking ：

The maximum value of continuous addition we require , So let's first clarify one thing , First number + The second number > The second number , Such a continuous number will be the largest . At the same time, we set a number storage maximum , Finally, you can go back

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
        vector<int> dp(array.size(), 0);// Open up a and array The same size vector Array dp
        dp[0] = array[0];
        int maxsum = dp[0];
        for(int i = 1; i < array.size(); i++){
            // Judge the first number + Whether the second number is greater than the second number itself 
            dp[i] = max(dp[i - 1] + array[i], array[i]);
            // See who is bigger than the sum of the two numbers 
            maxsum = max(maxsum, dp[i]);
        }
        return maxsum;
    }
};

The illustration ：