LeetCode53——Maximum Subarray——3 different methods

这道题目让我们求出一个线性数组中最大的连续子数组的和，题目要求如下：

这道题的题目很简单，解法也有多种，在这里总结3种解法去解决这个问题，在比较中加深对不同思路算法的理解，这三种算法是动态规划、模拟法、滑动窗口。
首先是动态规划法，正如我们之前提过的，递推形式的动态规划基本上就是三部曲：
1.确定DP数组的含义
2.递推奠基
3.基于递推方程来进行反复递推，直到最终答案
就这道题而言，DP[i]的含义是以nums[i]为结尾的最大的连续子数组的和，注意一定要以nums[i]为子数组的最后一个元素。在此基础上，我们可以得到递推方程：
DP[i] = max(DP[i-1] + nums[i], nums[i]);
也就是说，我们一定要以nums[i]为子数组最后一个元素，这个子数组的最大值可能情况有两种，第一是DP[i-1] + nums[i]，也有可能就是nums[i]本身，我们取这两者中的较大者(其实这里细想一下，当DP[i-1]是负数的时候，DP[i-1] + nums[i] < nums[i]一定成立，意识到这一点有利于理解下面的两种不同解法)。

现在有了DP数组的含义，也明确了递推关系，那么我们就可以开始完成动态规划版本的代码了。其实这里还有一个技巧，我们注意到DP[i]的取值只可能和DP[i-1]有关，且此递推只扫描一次数组nums。那么我们可以不必开辟一个数组，而只是用单个变量DP来反复记载以上一个数字为结尾的子数组最大值，这样将DP算法的空间复杂度降到了O(1)。还要注意，我们最终求得的结果并不是DP完成最后一次迭代的值，完成最后一次迭代时DP的值表示以nums最后一个元素为结尾的子数组的最大和，这不一定是所有情况下的最大值。我们要取得是全局最大值，这要求我们在每次迭代中都要进行一次最大值的更新：

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

全部代码如下：

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;
    }

以下的两种方法都基于一个事实，如果序列a1…an是我们最终求得的子序列，那么它的任意前缀之和总不可能是负值。这点可以使用反证法证明，假设a1…ax是a1…an的一个前缀且Σ(a1…ax) < 0
那么我们抹去a1…ax这个前缀，剩下序列的和一定大于a1…an的和，这就反证了a1…an不是最终结果，因为ax+1… an大于之前的a1…an。

第二种算法是模拟法，也就是我们真实的去模拟一下子序列加的过程，核心思想就是上面反证法证明的这一段，代码如下：

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累计了当下前缀序列的和，可以看到如果PresentValue<0，我们认定这绝不可能是最终的子序列和，因为它的前缀小于0了，这时候我们将PresentValue清0表示从最新的一个元素开始累加，同时保证了MaxValue的即时更新。
滑动窗口算法和模拟法大同小异，无非就是将窗口下界的滑动时机确定为前缀和小于0的时候，代码如下：

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;
  }

以上就是这道题的三种不同解法，真是一道非常经典的题目。