最大子序列是什么?
题目即内容
[解决办法]
大致可以这样理解
算法思想:由于最大子串的特性,我们不妨假设经过我这个算法算出来的子串不符合要求,那么必定在串中存在一点或者两点,使得头或者尾指针移动到这两点时,构造出来的新串的sum更加大。此时,只要把我们的串的开始或者结尾的位置调整一下,便可以获得sum更大的新串。
我们这个算法就是先假定已经获得一个比较完美的串,接下来就是寻找更合理的移动点。
1、分别求出每两个数字字间的差,首先计算从左到右减,然后计算从右到左减,分别储存两个数组值。这里为了简化,可以考虑将多个连续的正数求合并当成新的数放回去。
2、定义串首指针,指向子串首位。定义一个 int temp 变量
3、step by step地向右移动指针,同时temp变量每次都加上从左到右减的差(通过查表得到)
4、如果temp为正,证明此时首指针若移动到该位置,子串的值会更大,那么,把串首指针定义成当前位置,并重复3。否则继续移动但不改变串首位置。
5、直到遍历完整个子串。
6、定义串尾指针,用上述类似的算法计算出最佳位置。
7、将串首串尾连接起来,就是最佳子串。