kadane算法

题目：

给你一个整数数组nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部分

nums=input() def kan(n): if not n: return 0 max_sum=n[0] now_sum=n[0] for i in n[1:]: now_sum=max(i,now_sum+i) max_sum=max(max_sum,now_sum) return max_sum print(kan(nums))

max_sum:目前所见过的最大子数列和 now_sum：以i-1为结尾的子数列的最大和

1，kadane算法每一步只考虑n[i]和n[i]+“以n[i-1]为结尾的最大子数组的和”这两个谁大-----有点像函数递归

假设now_sum=i说明i>now_sum+i说明与其实将i加到上一个子数列中不如以i为开头重开一个子数列

2.为什么是”以n[i-1]“为结尾的最大数组？

因为题目要的是连续的子数列和

3，为什么要从list的第2项（索引为1）来遍历？

因为第一次选择只能选n[0]