53. 最大子序和
'''
第二次做这个题,我对这个题完全一点印象都没有,所以怎么办呢?
当然是再想一遍白
'''
'''
思路1:
可以看到,找到具有最大和的连续子数组
--也就是说如果你从右往左找最大的,那么一定是绕不过每一个数的(除非不选)
如:[-2,1,-3,4,-1,2,1,-5,4]
从右往左看:
[2,4,3,6,2,3,1,-1,4]
就是如果你想要过去这个位置,就一定要看一下后面能不能变大,就是说后面的该位置的最大值是不是正数是不是
我能走下去的依据
'''
#这个代码的本质是动态规划
#还有一种分治的写法,不过感觉挺难,先放着
def fun1(nums):
max=nums[len(nums)-1]
for i in reversed(range(len(nums)-1)):
if nums[i+1]>0:
nums[i]=nums[i]+nums[i+1]
if nums[i]>max:
max=nums[i]
return max
fun1([-2,1,-3,4,-1,2,1,-5,4])
====================================================================================================================================================================================================================================
在这里插入代码片
