這一章節(jié)會學(xué)習(xí)關(guān)于動態(tài)規(guī)劃相關(guān)問題的算法漓帚。先簡單后困難母债。
53. 最大子序和
難度簡單
給定一個整數(shù)數(shù)組 nums ，找到一個具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個元素）尝抖，返回其最大和毡们。
示例:
輸入: [-2,1,-3,4,-1,2,1,-5,4]
輸出: 6
解釋: 連續(xù)子數(shù)組 [4,-1,2,1] 的和最大，為 6昧辽。
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
'''
貪心,如果前面數(shù)之和小于0, 則拋棄前面數(shù),以當(dāng)前數(shù)為起點(diǎn),記錄最大數(shù); 如果大于0, 則加上當(dāng)前數(shù).
'''
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為結(jié)尾的最大子序列之和
dp思路, 如果前面的數(shù)大于0, 則dp=當(dāng)前數(shù)加上前一個數(shù). 表示當(dāng)前數(shù)之前最大子序列之和
如果前面的數(shù)小于0, 則當(dāng)前數(shù)為最大子序列之和.
'''
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)
