题目链接:https://leetcode-cn.com/problems/maximum-subarray/
描述:给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。
- 解法一: 采用动态规划,把每一次的滑动的最大值记录下来。
class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if nums == None or len(nums) == 0:
return None
slist = [nums[0]]
max_sum = nums[0]
for i in range(1, len(nums)):
if slist[i - 1] > 0:
slist.append(slist[i - 1] + nums[i])
else:
slist.append(nums[i])
if max_sum < slist[i]:
max_sum = slist[i]
return max_sum
- 解法二: 在DP上优化。其实DP数组也是记录s。
如果 s > 0,则说明 s 对结果有增益效果,则 s 保留并加上当前遍历数字
如果 s <= 0,则说明 s 对结果无增益效果,需要舍弃,则 s 直接更新为当前遍历数字。
class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if nums == None or len(nums) == 0:
return None
max_sum = nums[0]
s = 0
for i in range(len(nums)):
if s > 0:
s += nums[i]
else:
s = nums[i]
max_sum = max(max_sum, s)
return max_sum
网友评论