Ex42 连续子数组的最大和

题目描述

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)。

解题思路

使用动态规划，得到如下公式： \(maxs(i)= \begin{cases} nums[i], & if\ i\ =\ 0\ or\ maxs[i-1]\ \le\ 0\\ nums[i]+maxs[i-1], & if\ i\ \ne\ 0\ and\ maxs[i-1]\ >\ 0 \end{cases}\) 另外，如果进一步优化的话，可以将max和上一个max保存下来，不再使用一个数组（vector）来保存。

代码

class Solution
{
public:
  int
  maxSubArray (std::vector<int> &nums)
  {
    int max = nums[0], prev = nums[0];
    for (std::vector<int>::size_type i = 1; i < nums.size (); ++i)
      {
        if (prev <= 0)
          {
            prev = nums[i];
            max = max > prev ? max : prev;
          }
        else
          {
            prev += nums[i];
            max = max > prev ? max : prev;
          }
      }
    return max;
  }
};

结果

执行结果：通过

执行用时：32 ms, 在所有 C++ 提交中击败了99.87%的用户

内存消耗：23 MB, 在所有 C++ 提交中击败了30.33%的用户

另一种解法

解题思路

这个想法比动态规划更复杂一些，有很多小的注意点，但是也比较直观。

• 现保存第0个作为当前最大值cur和全局最大值max。
• 遍历所有的数：
• 如果当前值是大于0的话，
  • 如果当前最大值小于0，把cur设为当前值；
  • 否则，cur加上当前值；
  • 更新max。
• 如果当前值小于0，且绝对值小于cur的话，
  • 更新max；
  • cur加上当前值。
• 否则，
  • 更新max；
  • cur设为当前值。

代码

class Solution
{
public:
  int
  maxSubArray (std::vector<int> &nums)
  {
    int cur = nums[0], max = nums[0];
    for (int i = 1; i < nums.size (); ++i)
      {
        if (nums[i] >= 0)
          {
            if (cur < 0)
              {
                cur = nums[i];
              }
            else
              {
                cur += nums[i];
              }
            max = cur > max ? cur : max;
          }
        else if (nums[i] < 0 && -1 * nums[i] < cur)
          {
            max = cur > max ? cur : max;
            cur += nums[i];
          }
        else
          {
            max = cur > max ? cur : max;
            cur = nums[i];
          }
      }
    return cur > max ? cur : max;
  }
};

结果

执行结果：通过

执行用时：44 ms, 在所有 C++ 提交中击败了86.75%的用户

内存消耗：22.8 MB, 在所有 C++ 提交中击败了45.77%的用户