Maximum sum of continuous subarray of sword finger offer (2)

The maximum sum of successive subarrays ( Two )

Subject requirements ：
Enter a length of n Integer array array, One or more consecutive integers in an array form a subarray , Find a continuous subarray with the largest sum .
1. Subarray is continuous , such as [1,3,5,7,9] The subarrays of are [1,3],[3,5,7] wait , however [1,3,7] It's not a subarray
2. If there are multiple consecutive subarrays with the largest sum , Then return the longest , The data of this question ensure that there is only one
3. The minimum length of the subarray defined by this question is 1, There is no empty subarray , That there is no [] Is a sub array of an array
4. The returned array is not included in the space complexity calculation

Answer key ：
The title has two requirements ：

1. Calculate and record the sum of the largest array
2. Record the starting and ending positions of the largest array sum

The key ：

• use dp Array to store the maximum array sum of each element in the solution array
• use maxsum Variable to store the largest array and
• use left、right Variable to record the starting position and target position of the sliding array （ That is, the starting and ending positions of the array that is calculating the sum ）
• use resl、resr Variable to record the starting and ending positions of the longest array of the current maximum array and
• If dp The sum of the array stored in the array is greater than maxsum, Or equal to maxsum And the length is greater than the longest array of the current stored maximum array and , Update resl、resr and maxsum Value
• If the current element value is added to the previous array and , Note that the sum of the previous array is negative , The maximum array sum should be restarted from the current element , therefore dp[i] The value of should be the value of the current element , also left=i;

Solution code ：

class Solution {
public:
   /**
    *  The class name in the code 、 Method name 、 The parameter name has been specified , Do not modify , Return the value specified by the method directly 
    *
    * 
    * @param array int integer vector 
    * @return int integer vector
    */
   vector<int> FindGreatestSumOfSubArray(vector<int>& array) {
       // write code here
       vector<int> dp(array.size(),0);
       int left=0,right=0,resl=0,resr=0;
       dp[0]=array[0];
       int maxsum=array[0];
       for(int i=1;i<array.size();i++){
           right++;
           dp[i]=max(dp[i-1]+array[i],array[i]);
           if(dp[i-1]+array[i]<array[i]){
               left=i;
           }
           // If you add i The value of is greater than or equal to the maximum value, but the length is greater than the length of the maximum array 
           if(dp[i]>maxsum || (dp[i]==maxsum && (right-left)>(resr-resl))){
               maxsum=dp[i];
               resl=left;
               resr=right;
           }
       }
       vector<int> resarray(array.begin()+resl,array.begin()+resr+1);
       return resarray;
   }
};