有一个数组集合 [3, 1, -2, 4, 6, -4, -2, -7, 5, 6, -3, 2]
希望能求得集合内某个范围 下标N~M的最大值可能是多少.
在实际生活中可能遇到这个情况之一的是股票,
某月 1号, 股价上涨3块.
2号, 股价上涨1块.
3号, 股价下跌2块.
4号, 股价上涨4块.
5号, 股价上涨6块.
6号, 股价下跌4块.
7号, 股价下跌2块.
8号, 股价下跌7块.
9号, 股价上涨5块.
10号, 股价上涨6块.
11号, 股价下跌3块.
12号, 股价上涨2块.
想知道这13天, 只进行一次买卖的话. 哪天买入, 哪天卖出. 可以获得最大收益.
然后来分析一下这个情况, 第一天赚了3, 第二天又赚了1, 那么这时, 我总共赚了4. 第三天, 虽然跌了2, 但是我实际上, 还是赚了2. 第四天, 又赚了4, 这时总共赚了6了. 虽然中途有下跌, 但是下跌的数值, 跟第一二天上涨的数值比, 还是小于的, 所以还是多赚了2块. 第五天, 又赚了6块, 这时. 总共赚了12块了. 第六天, 下跌了4, (+8). 第七天, 下跌2, (+6). 第八天, 下跌7, (-1).此时, 开始亏钱了. 那么, 总第八开始, 前面的日期. 总的来说, 是亏钱的. 就不计算在内了, 需要重新计算.
依据前几天的情况, 一直到第八天才亏光. 但是这8天里, 赚到的最大值, 是12. 那么从 第一天, 到第5天. 是前8天的最大范围.
第九天, 赚了5 (+5). 第十天, 赚了6 (+11). 第十一天, 亏了3(+8). 第十二天, 赚了2 (+10).
由此看到第九天 到 第十天, 一度赚到了11, 是最大值. 并且大于前8天的最大值8. 所以. 第九,十两天赚到是最大值.
如何计算呢
这个最大值的范围, 一定是从一个正数, 到另一个正数的范围. 因为负数是减嘛, 如果一开始就减, 那就没有必要了. 所以首先我们 循环整个数组寻找第一个正数, 找到之后, 记录下标和总和. 然后加上后一个数, 如果总和大于0, 说明总体是上涨的. 如果小于0. 那么是下跌了, 就不要了, 并且初始化记录, 重新开始. 以此往复.
在记录的时候呢, 记录了总和, 用来判断总体是不是大于0, 是否有必要带着前面的集合. 并且, 要同时记录最大值.
int max = 0; 最大值
int count = 0; 总和
count += ary[i]; 数值相加, 看看是否大于0
if ( count > max ){
max = count; //出现更大的数, 记录下来
}
这样能得到最大的值, 其次, 就是获取区间范围. 这个就是记录方法了. 我就不在此描述了
