Kadane's algorithm学习

Kadane’s algorithm

简单来说就是用来计算数组中的连续子数组之和最大是多少

vector<int> vec; int temp = 0,ans = 0; for(int i=0;i<vec.size();++i){temp = max(temp+vec[i],vec[i]);ans = max(temp,ans); } return ans;

循环的第一行就是用来比较当前位置的值和前面数组之和的大小，如果：
1、temp > 0，一个正数加一个vec[i] 大于 vec[i]
2、temp < 0：
（1）vec[i]>0：一个负数加一个正数小于这个正数本身；
（2）vec[i]<0：一个负数加另一个负数小于这两个负数，这样的话重新设定起点了，前面一堆都是负数，没必要加上去。

第二行：用来保存找查找过程中最大值的。
temp有可能增大后减少，这时需要保存一个ans来记录最大值是多少。
到时候就可以获得这个ans的值来确定子数组和最大为多少。

总结

以上是生活随笔为你收集整理的Kadane's algorithm学习的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。