LeetCode53——Maximum Subarray——3 different methods

This topic lets us find a linear array The sum of the largest continuous subarray , The questions are as follows ：

The title of this problem is very simple , There are many solutions , To sum up 3 A solution to this problem , Deepen the understanding of different algorithms in comparison , These three algorithms are Dynamic programming 、 Simulation 、 The sliding window .
The first is dynamic programming , As we mentioned before , Recursive dynamic programming is basically a trilogy ：
1. determine DP The meaning of array
2. Recurrence Foundation
3. Based on the recurrence equation to carry out repeated recurrence , Until the final answer
As far as this question is concerned ,DP[i] The meaning is With nums[i] Is the sum of the largest contiguous subarray at the end , Pay attention to nums[i] Is the last element of the subarray . On this basis , We can get the recurrence equation ：
DP[i] = max(DP[i-1] + nums[i], nums[i]);
in other words , We must take nums[i] For the last element of the subarray , There are two possible situations for the maximum value of this subarray , The first is the DP[i-1] + nums[i], It could also be nums[i] In itself , We take The larger of the two ( Actually, think about it here , When DP[i-1] When it's a negative number ,DP[i-1] + nums[i] < nums[i] It must be true , Realizing this helps to understand the following two different solutions ).

There is now a DP The meaning of array , It also clarifies the recursive relationship , Then we can start to complete the dynamic planning version of the code . Actually Here's another trick , We noticed that DP[i] The value of can only be equal to DP[i-1] of , And this recursion only scans the array once nums. Then we don't have to open up an array , Instead, just use a single variable DP To repeatedly record the maximum value of the subarray ending with the above number , This will DP The space complexity of the algorithm is reduced to O(1). Also pay attention to , The result we finally got Not at all DP The value of completing the last iteration , When the last iteration is completed DP The value of is expressed in nums The last element is the maximum sum of the ending subarray , This is not necessarily the maximum in all cases . We want to get the global maximum , This requires us to update the maximum value in each iteration ：

MaxValue = max(MaxValue, DP = max(nums[i], DP + nums[i]));

All codes are as follows ：

int maxSubArray(vector<int>& nums) {
    
        if(nums.size() == 1)
            return nums[0];

        /*solution1 : DP*/
        /*1&2：DP means the maximum sum and DP's initial value is nums[0]*/
        int MaxValue = nums[0];
        int DP = nums[0];

        /*3.start recursion*/
        for(int i = 1 ; i < nums.size() ; ++i)
            MaxValue = max(MaxValue, DP = max(nums[i], DP + nums[i]));

        return MaxValue;
    }

Both of the following methods are based on one fact , If the sequence a1…an Is the subsequence we finally get , So it's The sum of any prefix can never be negative . This can be used Reduction to absurdity prove , hypothesis a1…ax yes a1…an A prefix of and Σ(a1…ax) < 0
Then let's erase a1…ax The prefix , The sum of the remaining sequences must be greater than a1…an And , This is the opposite a1…an Not the end result , because ax+1… an Greater than the previous a1…an.

The second algorithm is simulation , That is, we really simulate the process of sequence addition , The core idea is the paragraph proved by the above counter evidence , The code is as follows ：

int maxSubArray(vector<int>& nums) {
    
        if(nums.size() == 1)
            return nums[0];

        /*solution 2 ：simulation*/
        int PresentValue = nums[0], MaxValue = nums[0];
        for(int i = 1 ; i < nums.size() ; ++i)
        {
    
             if(PresentValue < 0)
                 PresentValue = 0;
             PresentValue += nums[i];
             MaxValue = max(MaxValue, PresentValue);
        }
        return MaxValue;

PresentValue The sum of the current prefix sequence is accumulated , You can see if PresentValue<0, We decided that this could never be the final subsequence and , Because its prefix is less than 0 了 , At this time we take PresentValue clear 0 It means to accumulate from the latest element , At the same time, it guarantees MaxValue Instant updates .
Sliding window algorithm and simulation method are similar , It's nothing more than The sliding time of the lower bound of the window is determined as the prefix and less than 0 When , The code is as follows ：

int maxSubArray(vector<int>& nums) {
    
     if(nums.size() == 1)
         return nums[0];

     /*solution 3 : sliding window*/
     int MaxValue = nums[0];

     // the sum of all the elements inside window
     int PresentValue = nums[0];

      // init the lower and upper bound of window
      int Left = 0, Right = 1;

      // start silding window
      while(Right < nums.size())
      {
    
          if(PresentValue < 0)
          {
    
              // modify the lower bound of window
              Left = Right;
              PresentValue = 0;
          }
          PresentValue += nums[Right];
          MaxValue = max(MaxValue, PresentValue);
          ++Right;
      }
      return MaxValue;
  }

These are three different solutions to this problem , It's really a very classic topic .