【LeetCode】53、最大子序和

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.

  • 中文:

    给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

  • 示例

    Example:

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

    如果你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的分治法求解。

解题思路

思路一

遍历数组,用curSum维护当前位置累加的和,当curSum<0时,将其置为0,重新开始累加,每次都更新全局最大值。

顺序遍历整个数组,当遍历到第i个值时,有两种情况:

  1. 之前遍历过程中的curSum始终大于0,假设当前子序列为a,a+1,a+2,...,b-2,b-1,b,此时考虑所有可能:

    • 以当前子序列开头为开头,以中间任一处结尾的序列,如a,a+1,a+2,...b-2:这种情况一致在遍历过程中保存更新;
    • 以当前子序列结尾为结尾,以中间任一处开头的序列,如a+2,...,b-2,b-1,b:这种情况一定小于当前的完整子序列的和,因为前面缺失的部分的和一定是大于0的(讨论的前提就是遍历过程加和始终大于0);
    • 以中间元素为开头和结尾的序列,如a+2,...,b-2:这种情况,首先按照前一条讨论,补全前面缺失的部分,之后就变成了第一条讨论的情况;

    也就是说,i前面的所有可能序列情况都已经考虑到了;

  2. curSum出现小于0的情况,此时由于已遍历过的连续子序列加和<0,则遍历过的这个连续子序列不能完整的被包含到新形成的序列中了;而是否要全部放弃,还是保留末尾的部分元素?参考之前的讨论,以当前子序列结尾为结尾,以中间任一处开头的序列的加和是小于完整子序列的,也就是说是<0的,因为此时遍历过的连续子序列需要全部放弃,即curSum置0,并重新开始累加。

其中,每次curSum<0时的下一位置即为和最大的子序列的开始,每次curSum>maxSum时的位置即为和最大的子序列的结尾。

代码提交

Python3,用时96ms,内存13.6M

时间复杂度:$O (n) $

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
if not nums:
return None
if len(nums) == 1:
return nums[0]

maxSum = nums[0]
curSum = 0
for i in range(len(nums)):
curSum += nums[i]
maxSum = max(maxSum, curSum)
if curSum < 0:
curSum = 0
return maxSum

思路二

动态规划,用tempSum保存以第i个元素结尾的最大连续子序列的和,假设对于元素i,其前面的所有元素结尾的序列和都已经得到,则以第i个元素结尾的子序列的和要么是以第i-1个元素结尾的和最大的子序列加上当前元素,要么就是当前元素本身,即tempSum[i] = max(tempSum[i-1]+nums[i], nums[i])。(实际等价于看以i-1个元素结尾的和最大的子序列的和是否小于0,等价于思路一了)当i=0时,最大子序列和即为tempSum[0] = nums[0]

代码提交

Python3,用时104ms,内存14.2M

时间复杂度:$O (n) ​$

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
if not nums:
return None
if len(nums) == 1:
return nums[0]

tempSum = []
tempSum.append(nums[0])
for i in range(1, len(nums)):
tempSum.append(max(tempSum[i-1]+nums[i], nums[i]))
return max(tempSum)

可以直接用nums来保存子序列最大和,能节约一点内存,如下:

1
2
3
4
5
6
7
8
9
10
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
if not nums:
return None
if len(nums) == 1:
return nums[0]

for i in range(1, len(nums)):
nums[i] = max(nums[i-1]+nums[i], nums[i])
return max(nums)

思路三

提示说可以尝试用分治法,那么就将整个数组不断切分成子数组,最后选最大值返回。

用二分法切分数组,最大子序和要么在左半部分,要么在右半部分,要么横跨左右两部分(既包含左侧的最后一个元素,也包含右侧的第一个元素),返回这三种情况的最大值即可。

横跨左右两部分的情况,可以从中间位置逐次向左右两侧遍历,并更新最大值。

代码提交

Python3,用时272ms,内存13.7M

时间复杂度:$O(n\log n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
if not nums:
return None
if len(nums) == 1:
return nums[0]

left = 0
right = len(nums)-1

maxSum = self.divide(nums, left, right)
return maxSum

def divide(self, nums, left, right):
# 切分到只有一个元素时,返回
if left == right:
return nums[left]

# 确立中心点
center = (left + right)//2

# 子序列完全在左侧的最大和
leftMax = self.divide(nums, left, center)

# 子序列完全在右侧的最大和
rightMax = self.divide(nums, center+1, right)

# 子序列横跨左右两侧的最大和
# 从中间点逐次向左边界靠近
leftSum = 0
leftBorderSum = 0
for i in range(center-1, left-1, -1):
leftSum += nums[i]
leftBorderSum = max(leftSum, leftBorderSum)
# 从中间点逐次向右边界靠近
rightSum = 0
rightBorderSum = 0
for i in range(center+1, right+1):
rightSum += nums[i]
rightBorderSum = max(rightSum, rightBorderSum)
centerMax = leftBorderSum + nums[center] + rightBorderSum
return max(leftMax, centerMax, rightMax)
-------------本文结束感谢您的阅读-------------
0%