样例:
给出数组[−2,2,−3,4,−1,2,1,−5,3],符合要求的子数组为[4,−1,2,1],其最大和为6
要求时间复杂度为O(n)
想了一会并没有特别好的方法,想了一个用双指针的方法,...基于这三种情况分析,我们可以采用这样的思路,先设置一个max,把这个数设置为INT_MIN,设置sum作为变量来记录当前得到的字数组的和,一旦sum>max,就可以更新max,这样就能保证max是最大字数组的和...这样说来不是很直观,我们可以注意这样一个事实:我们要找的子数组的前面的几个数(不管是几个),和肯定不能是负的,如果是负的,那么去掉岂不是得到的和更大,这样就能理解为什么一旦发现前面的字数组为负的话,就丢掉...(不能同时剔除两个‘比如[-1,-3,-1]',如果同时剔除两个1,得到的最大值可能是-3,实际上是-1,但是同时被剔除掉了),我是用这个方法试了一些数据,感觉还挺靠谱,于是写了一下,中间用迭代器的程序还不对...res_max;
// write your code here
}
----
振哥指导了一个思路说是当两端相同的话,任意去掉一个是不明智的,后来我想了一下确实是这样的,因为如果恰好有一个就是最大子数组之列又恰好被去掉呢