Sword finger offer:[day 9 dynamic planning (medium)] --- > maximum sum of continuous subarrays

---

One 、 Title Description

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 ：

 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<=\mathrm{a}\mathrm{r}\mathrm{r}.\mathrm{l}\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h}<=10^5$
$-100<=\mathrm{a}\mathrm{r}\mathrm{r}[\mathrm{i}]<=100$

Two 、 Thought analysis

Ideas

In the previous data structure blog ( Link to ： The maximum sum of successive subarrays ： Three methods ) There are three ways to solve the maximum sum of continuous subsequences , Its time complexity and space complexity are as follows ：

The time complexity required for the topic is O(N), So we use dynamic programming .
State definition ： Set up a dynamic programming list dp,dp[i] Represented by elements nums[i] Is the maximum sum of consecutive subarrays at the end .
Transfer equation ： if dp[i-1]≤0, explain dp[i-1] Yes dp[i] Produce negative contribution , namely dp[i-1]+nums[i] Not so good nums[i] Itself big .
---- When dp[i-1]>0 when ： perform dp[i]=dp[i-1]+nums[i]
---- When dp[i-1]≤0 when ： perform dp[i]=nums[i]
The initial state ：dp[0]=nums[0], That is to nums[0] The maximum sum of consecutive subarrays at the end is nums[0].
Return value ： return dp The maximum value in the list , Represents the global maximum .

Reduced space complexity ：
because dp[i] Only with dp[i-1] and nums[i] It matters , Therefore, the original array can be nums Used as a dp list , That is, directly in nums You can modify it on the . As omitted dp Extra space used by the list , So the spatial complexity goes from O(N) Down to O(1).
case analysis ：










Complexity analysis ：
Time complexity $\mathrm{O}(\mathrm{N})$： Linear traversal array nums You can get results , Use O(N) Time .
Spatial complexity $\mathrm{O}(1)$： Use extra space of constant size .

3、 ... and 、 The overall code

The overall code is as follows

int maxSubArray(int* nums, int numsSize){
    
    int max = nums[0]; // Used to record the largest child columns and 
    int tmp = nums[0]; // Used to record dp[i] Value 
    int former = 0;    // Used to record dp[i-1] Value , about dp[0] for , In front of the dp[-1]=0

    for(int i = 0; i < numsSize; i++){
    
        tmp = nums[i];  // Record the value of the current item 
        if (former > 0) tmp+=former;  // If dp[i-1] Greater than 0, Then add dp[i-1]
        if (tmp > max) max=tmp;  // If tmp Greater than max, Will max Assign a value to tmp
        former = tmp;   // Move to next , to update former value 
    }
    return max;
}

function , The test passed