求最大子数组
2017-10-11 本文已影响6人
chenhh6701
注意:
1.因为数组中元素要合并,所以要用2个数组分别记录合并的信息
步骤:
1.现将数值连续的元素正正相加,负负相加的模式合并整理为正负数交替的新数组{正,负,正...,正,负,正 },同时记录下合并信息,去掉两端负数(不会用到)
2.将数值简化 。 取3个连续的数,如果中间数的绝对值小于其他2个就直接相加(+-+和-+-)--> (+ 和 -)
3.将第2步的究极版本比大小就好
优化:
第2步可以一次循环对比,也可以多次循环对比