🍥

Hang Zhang

genius.

Data Structure and Algorithm

maxSubArray

53. 最大子数组和

算法

定义状态：
- 用变量 last 表示以当前元素结尾的最大子数组和
- 用变量 res 表示全局最大子数组和
状态转移方程：
- 对于每个元素 num，当前的 last 值可以由以下两种情况决定：
  - 单独包含当前元素：如果此前的 last 为负数，则舍弃
  - 包含当前元素并延续之前的子数组：如果此前的 last 为正数，则将当前元素加入子数组
- 状态转移方程：last = max(num, last + num)
更新全局最大值：
- 在遍历每个元素后，更新全局最大值 res 为：res = max(res, last)

复杂度分析

时间复杂度

单次遍历：仅需遍历数组一次，时间复杂度为 O(n)

空间复杂度

只使用了 res 和 last 两个变量，空间复杂度为 O(1)

C++ 代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class Solution
{
public:
    int maxSubArray(vector<int>& nums)
    {
        int res = INT_MIN; // 全局最大子数组和
        int last = 0;      // 当前子数组和
        for (int num : nums)
        {
            last = std::max(num, last + num); // 动态更新以当前元素结尾的最大子数组和
            res = std::max(res, last);       // 更新全局最大值
        }
        return res;
    }
};

Python 代码

1
2
3
4
5
6
7


class Solution:
  def maxSubArray(self, nums: List[int]) -> int:
    res, last = nums[0], 0
    for x in nums:
      last = max(x, last + x)
      res = max(res, last)
    return res

Go 代码

1
2
3
4
5
6
7
8


func maxSubArray(nums []int) int {
  res, last := nums[0], 0
  for _, x := range nums {
    last = max(x, last + x)
    res = max(res, last)
  }
  return res
}

JavaScript 代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function (nums) {
  let res = nums[0],
    last = 0;
  for (let x of nums) {
    last = Math.max(x, last + x);
    res = Math.max(res, last);
  }
  return res;
};