这一章节会学习关于动态规划相关问题的算法。先简单后困难。
53. 最大子序和
难度简单
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
'''
贪心,如果前面数之和小于0, 则抛弃前面数,以当前数为起点,记录最大数; 如果大于0, 则加上当前数.
'''
if not nums:
return
n = len(nums)
pre = max_num = nums[0]
for i in range(1, n):
pre = max(nums[i], pre + nums[i]) #
max_num = max(max_num, pre)
return max_num
def maxSubArray1(self, nums: List[int]) -> int:
'''
dp[i] 表示以i为结尾的最大子序列之和
dp思路, 如果前面的数大于0, 则dp=当前数加上前一个数. 表示当前数之前最大子序列之和
如果前面的数小于0, 则当前数为最大子序列之和.
'''
if not nums:
return
n = len(nums)
if n == 1:
return nums[0]
for i in range(1, n):
if nums[i-1] > 0:
nums[i] = nums[i] + nums[i-1]
return max(nums)
