目录
润到分治篇了
依稀记得，分治分为分解、解决和合并3个
运用动态规划求解比较方便
liwei神 动态规划讲解的神！！！
动态规划求解5部曲：
「状态定义」（定义子问题）
dp[i]：表示以 nums[i] 结尾 的 连续 子数组的最大和。
为什么要定义结尾？而不是开头或者中间？
开头----子问题间没有相关性
中间---不知道nums[i]在子数组中是第几个元素
「状态转移方程」（描述子问题之间的联系）
求最大值
「初始化」
dp[0] 根据定义，只有 1 个数，一定以 nums[0] 结尾，因此 dp[0] = nums[0]。
「输出」
dp[0]、dp[1]、……、dp[n - 1] 取max
「是否可以空间优化」
使用「滚动变量」的方式将代码进行优化。
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
#优化前
n=len(nums)
if n==0:
return 0
#子问题
dp=[0 for _ in range(n)]
#初始化
dp[0]=nums[0]
#转移方程
for i in range(1,n):
dp[i]=max((dp[i-1]+nums[i]),nums[i])
#输出
return max(dp) 
无后效性
分治法：
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
n=len(nums)
if n==0:
return 0
return self.max_sub(nums,0,n-1)
def max_sub(self,nums,left,right):
if left==right:
return nums[left]
mid=(left+right)//2
return max(self.max_sub(nums,left,mid),
self.max_sub(nums,mid+1,right),
self.max_cross(nums,left,mid,right))
def max_cross(self,nums,left,mid,right):
#必须包含nums[mid]
#往左尽力扩散，往右也是，相加即可
left_max=0
start_left=mid-1
s1=0
while start_left>=left:
s1+=nums[start_left]
left_max=max(left_max,s1)
start_left-=1
right_max=0
start_right=mid+1
s2=0
while start_right<=right:
s2+=nums[start_right]
right_max=max(right_max,s2)
start_right+=1
return left_max+right_max+nums[mid] 
