maxiumn-subarray 和最大的子数组

题目

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2, 1, -3, 4, -1, 2, 1, -5, 4], 
the contiguous subarray [4, -1, 2, 1] has the largest sum = 6.

思路一

首先，可以直接两重循环，找到所有的子数组，然后计算出来和最大的那个，时间复杂度为O(n)，空间复杂度为O(1)。代码如下：

    int maxSubArray(vector<int>& nums) {
      if (nums.size() == 1) {
        return nums[0];
      }
      int result = -pow(2, 31);
      for (int i = 0; i < nums.size(); ++i) {
        int sum = 0;
        for (int j = i + 1; j < nums.size(); ++j) {
          sum += nums[j];
          if (sum > result) {
            result = sum;
          }
        }
      }
      return result; 
    }

思路二

举例子说明：

题目要求数组[-2, 1, -3, 4, -1, 2, 1, -5, 4]的任意连续子数组中和最大的那个连续子数组的和。

我们可以将该数组拆分成下面的数组：

[-2, 1, -3, 4, -1, 2, 1, -5, 4]
[-2, 1, -3, 4, -1, 2, 1, -5]
[-2, 1, -3, 4, -1, 2, 1]
[-2, 1, -3, 4, -1, 2]
[-2, 1, -3, 4, -1]
[-2, 1, -3, 4]
[-2, 1, -3]
[-2, 1]
[-2]

对于这里的每个数组，可以求出来它的每个以最后一个元素为结束的子数组，看哪一个子数组的和最大。

例如：

[-2, 1, -3, 4, -1, 2, 1], 它的以最后一个元素为结束的子数组有[-2, 1, -3, 4, -1, 2, 1], [1, -3, 4, -1, 2, 1], [-3, 4, -1, 2, 1], [4, -1, 2, 1], [-1, 2, 1], [2, 1], [1]，和最大的是[4, -1, 2, 1], 和为6。

[-2, 1, -3, 4, -1, 2], 它的以最后一个元素为结束的子数组有[-2, 1, -3, 4, -1, 2], [1, -3, 4, -1, 2], [-3, 4, -1, 2], [4, -1, 2], [-1, 2], [2], 和最大的是[4, -1, 2], 和为5。

相比前面的思路一，我们相当于倒序遍历了所有的子数组，但是, 我们并不需要O(n^2)的时间复杂度，因为很多重复的计算可以利用，只需要遍历一次，时间复杂度为O(n)，而重复的计算，可以用变量记下来, 空间复杂度为O(n)。

现在一步一步来求各个子数组array中, 最大子数组的和max, 要求array的子数组必须以array的最后一个元素结束

max([-2]), 明显为-2，子数组为[-2]
max([-2, 1]), 由于-2小于0，如果子数组以-2作为起点，肯定只会让和更小，所以应该以1作为起点，这里明显max([-2, 1]) = 1, 子数组为[1]
max([-2, 1, -3])，由于上面已经得出1作为起点更优，而1大于0，所以加上-3之后，目前max([-2, 1, -3]) = 1 + -3 = -2, 子数组为[1, -3]
max([-2, 1, -3, 4])，由于上面计算得到的最优值为-2，小于0，如果子数组以前面得出的结论作为起点，肯定只会让和更小，所以应该从4作为起点，目前max([-2, 1, -3, 4]) = 4, 子数组为[4]
max([-2, 1, -3, 4, -1])，由于上面计算得到的最优值为4，大于0，所以加上-1之后，目前max([-2, 1, -3, 4, -1]) = 4 + -1 = 3, 子数组为[4, -1]
max([-2, 1, -3, 4, -1, 2])，由于上面计算得到的最优值为3，大于0，所以加上2之后，目前max([-2, 1, -3, 4, -1, 2]) = 3 + 2 = 5, 子数组为[4, -1, 2]
max([-2, 1, -3, 4, -1, 2, 1])，由于上面计算得到的最优值为5，大于0，所以加上1之后，目前max([-2, 1, -3, 4, -1, 2, 1]) = 5 + 1 = 6, 子数组为[4, -1, 2, 1]
max([-2, 1, -3, 4, -1, 2, 1, -5])，由于上面计算得到的最优值为6，大于0，所以加上-5之后，目前max([-2, 1, -3, 4, -1, 2, 1, -5]) = 6 + -5 = 1, 子数组为[4, -1, 2, 1, -5]
max([-2, 1, -3, 4, -1, 2, 1, -5, 4])，由于上面计算得到的最优值为1，大于0，所以加上4之后，目前max([-2, 1, -3, 4, -1, 2, 1, -5, 4]) = 1 + 4 = 5, 子数组为[4, -1, 2, 1, -5, 4]

这个时候，我们再来看各个子数组的最大子数组的和，分别是1, -2, 3, 5, 6, 1, 5，最大的是6，对应的子数组是[4, -1, 2, 1], 就是题目的答案。

代码

    int maxSubArray(vector<int>& nums) {
      int result = nums[0];
      int *max = new int[nums.size()];
      max[0] = nums[0];
      for (int i = 1; i < nums.size(); ++i) {
        if (max[i - 1] > 0) {
          max[i] = max[i - 1] + nums[i];
        } else {
          max[i] = nums[i];
        }
        if (max[i] > result) {
          result = max[i];
        }
      }
      return result; 
    }

由于我们每一步都在根据上一步的结果做决策和规划，所以这叫做动态规则 。

文章目录

题目

思路一

思路二

代码