LeetCode 双刀流：53. Maximum Subarray

53. Maximum Subarray

接下来我们挑 53. Maximum Subarray 的题目，这个题目直接用穷举或暴力法可能会有时间上的疑虑。因此，需要思考如何用比较有效率的方法来解题。而这一题在解题的过程中，如何搭配算法的特性将所需的资讯暂存下来而不用每次都浪费回圈的时间进行运算。

先看一下题目描述

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum. A subarray is a contiguous part of an array.

再搭配范例理解题目

• Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

• Example 2:

Input: nums = [5,4,-1,7,8]
Output: 23

这个题目从范例中很好理解，要从一个阵列中找出总和最大的「subarray」，题目中也有特别补充「subarray 是指原阵列中连续部分所组成的阵列」。

开始实作

在理解完题目与条件之後，那我们下一步就开始「#初探直觉解」并且一起尝试「#刻意优化」的过程：

方法 ①：暴力法

第一种方法当然就是先用暴力法计算 subarray 的数值，将最大的那一组留下来。这里可以使用两层的回圈，将每一个点作为起点的所有可能列出来计算。

用 Python 实作一次

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        m = float("-inf");
        for i in range(len(nums)):
            s = 0;
            for j in range(i+1, len(nums)):
                s += nums[j]
                if s > m:
                    m = s
        return m;

也可以用 JavaScript 复刻一次

var maxSubArray = function(nums) {
  const len = nums.length;
  let max = -Number.MAX_VALUE;
  let sum = 0;
  for (let i = 0; i < len; i++) {
    sum = 0;
    for (let j = i; j < len; j++) {
      sum += nums[j];
      if (sum > max) {
        max = sum;
      }
    }
  }
  return max;
}

不过这样解法在跑范例的时候可以通过，但是实际上跑测资时会出现 Time Limit Exceeded 的错误。

方法 ②：累加法（Greedy）

第一种方法的的概念是「使用两层的回圈，将每一个点作为起点的所有可能列出来」，第二层回圈会将每一个位置後的每一种可能进行累加，例如以下这个例子：

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

第一个回圈会找出：

* -2
* 1
* -3
...

第二个回圈会从每一个位置在往後延伸：

* -2
  * -2 + 1
  * -2 + 1 + -3
  * -2 + 1 + -3 + 4 
  * -2 + ...

* 1
  * 1 + -3
  * 1 + -3 + 4 
  * 1 + ...

讲到这里，你有发现什麽了吗？对，没错，每次都从头开始找！但实际上「-2 + 1 + -3 + 4 」应该可以沿用「-2 + 1 + -3」累加的结果往後增加即可，第二种方法就是每回合只要往後累加新的元素进行比较就好。

用 Python 实作一次

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        maxSum = nums[0]
        curSum = nums[0]
        for num in nums:
            curSum = max(curSum + num, num)
            maxSum = max(maxSum, curSum)
        return maxSum

也可以用 JavaScript 复刻一次

var maxSubArray = function(nums) {
  var maxSum = nums[0],curSum = nums[0];
  for(let num of nums){
    curSum = Math.max(curSum + num, num);
    maxSum = Math.max(maxSum, curSum);
  }
  return maxSum;
};

方法 ③：累加法（DP）

第二种方法我们会用一个变数「curSum」来存放累加的结果，第三种方法我们进一步将累加的结果直接暂存在原阵列中。换句话说，利用原始的阵列将 subarray 加总的结果记录下来。

用 Python 实作一次

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        res = nums[0]
        for i in range(1, len(nums)):
            if nums[i-1] > 0:
                nums[i] = nums[i] + nums[i-1]
            res = max(res, nums[i])
        return res

也可以用 JavaScript 复刻一次

var maxSubArray = function(nums) {
  let res = nums[0];
  for (let i = 1; i < nums.length; ++i) {
    if (nums[i - 1] > 0)
      nums[i] += nums[i - 1];
    res = Math.max(res, nums[i]);
  }
  return res;
};

反思沉淀

这题想跟介绍是的除了穷举法/暴力法之外，我们常见有几种不同的方法可以来进行演算法的优化。这题用的分别是「Greedy（贪婪法）」与「Dynamic Programming（动态规划法）」，这里先用直觉的方法走过一次，後面再花比较多时间进行讨论。

举一反三看看相似题

最後可以从题目提供的相似题看一下有哪些类似的题目，适合作为你下一个尝试的练习：

• 121. Best Time to Buy and Sell Stock
• 152. Maximum Product Subarray
• 697. Degree of an Array
• 1749. Maximum Absolute Sum of Any Subarray

嗨，大家好！我是维元，一名擅长网站开发与资料科学的双栖工程师，斜杠於程序社群【JSDC】核心成员及【资料科学家的工作日常】粉专经营。目前在 ALPHACamp 担任资料工程师，同时也在中华电信、工研院与多所学校等单位持续开课。拥有多次大型技术会议讲者与竞赛获奖经验，持续在不同的平台发表对 #资料科学、 #网页开发 或 #软件职涯 相关的分享，邀请你加入 订阅 接收最新资讯。