53. 最大子數組和

給你一個整數數組 nums ，請你找出一個具有最大和的連續子數組（子數組最少包含一個元素），返回其最大和。
子數組是數組中的一個連續部分。

class Solution:def maxSubArray(self, nums: List[int]) -> int:ans = nums[0]tmp = nums[0]for i in range(1,len(nums),1):tmp = max(tmp+nums[i], nums[i])ans = max(ans, tmp)return ans

53. 最大子數組和

兩個不重合的連續子數組最大和

在上題基礎上，求解數組的兩個不重合的連續子數組和的最大值。
解題思路：
最開始的思路，就是將數組分為兩部分，分別求最大連續子數組和然后相加，時間復雜度為O(n^2)。
進一步優化：
1.構建兩個dp數組，分別表示從左到右，從右到左的連續子數組和的最大值。
2.遍歷不同的劃分點，計算最大值。
與上述類似思路的題目 135. 分發糖果

def maxtwo(nums):n = len(nums)def leftmax(l):dp = [0]*nt = 0ans = float('-inf')for i in range(n):t = max(l[i], l[i]+t)ans = max(t, ans)dp[i] = ansreturn dpdef rightmax(l):dp = [0]*nt = 0ans = float('-inf')for i in range(n-1,-1,-1):t = max(l[i], t+l[i])ans = max(t, ans)dp[i] = ansreturn dpleft = leftmax(nums)right = rightmax(nums)ans = float('-inf')for i in range(n-1):ans = max(ans, left[i] + right[i+1])return ans