题目

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

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