题意分析

  • 给出一个数组序列，找出和最大的连续子数组的和。并且要求时间复杂度O(n)（由于这个题目比较简单，所以我们重点放在如何解题上面）
  • 考点是差分前缀和，下面大家可以结合下面这个图来更好地理解什么是差分思想，其实这只是一个很基础的一个差分，差分思想还是很重要的，可以帮助我们更好地优化我们的代码。

思路分析

思路一

  • 我们直接用最朴素的方法进行求解，我们看到连续的数组，自然就很容易会想到利用前缀和的思想进行求解。我们先遍历一遍求出前缀和，然后利用一个二重循环枚举子数组的长度，维护一个最大值即可。

  • 代码如下，时间复杂度为O(n^2),空间复杂度为O(n)

    class Solution {
public:
  int FindGreatestSumOfSubArray(vector<int> array) {
      int len=array.size();
      // 特判为空的情况
      if(len==0){
          return 0;
      }
      vector<int> pre;
      pre.push_back(array[0]);
      int ans=pre[0];
      int sum=0;
      // 求前缀和
      for(int i=1;i<len;i++){
          sum=array[i]+pre[i-1];
          pre.push_back(sum);
          ans=max(ans,sum);
      }
      // 枚举连续数组的长度，维护最大值
      for(int i=0;i<len;i++){
          for(int j=i+1;j<len;j++){
              ans=max(ans,pre[j]-pre[i]);
          }
      }
      return ans;
  }
};

    我们发现，这种写法显然不尽如人意。所以我们要想办法进行优化。

思路二

  • 动态规划，现在，我们继续观察这个前缀和，我们发现其实可以用一个动态规划进行求解。dp[i]表示的是前i个位置所得到的最大的连续数组和。
    状态转移方程为dp[i]=max(dp[i1]+array[i],array[i]),我们用一个变量ans来维护我们需要求的值即可。根据这个我们写出一个优化的代码。

  • 时间复杂度O(n),空间复杂度O(n)

    class Solution {
public:
  int FindGreatestSumOfSubArray(vector<int> array) {
      int n=array.size();
      vector<int> dp;
      dp.push_back(array[0]);
      // 初始化
      int ans=dp[0];
      for(int i=1;i<n;i++){
          // 根据状态转移公式进行状态转移  
          dp.push_back(max(array[i],dp[i-1]+array[i]));
          // 维护最终的答案
          ans=max(ans,dp[i]);
      }
      return ans;
  }
};

思路三

  • 时间复杂度显然是不能继续优化了，但是我们发现其实空间复杂度还是可以继续进行优化的。我们发现，其实，我们并不需要多开一个动态数组，因为我们每次使用的时候我们都会发现其实我们最多只需要使用上一次状态就行了，对于更多的状态我们没有必要进行存储。所以我们可以只需要开一个int类型的变量来记录每个状态的值就行了。

  • 时间复杂度O(n),空间复杂度O(1)

    class Solution {
public:
  int FindGreatestSumOfSubArray(vector<int> array) {
      int n=array.size();
      // 初始化操作
      int ans=array[0];
      int sum=array[0];
      for(int i=1;i<n;i++){
          // 在上一种解法的前提下进行优化，维护最终的答案
          sum=max(array[i],sum+array[i]);
          ans=max(ans,sum);
      }
      return ans;
  }
};

最后，我们就由一开始很朴素的代码一步一步优化到如今的代码，其实很多很奇妙的算法也都是这样一步一步优化而来的，我认为这才是学习算法的乐趣。