大学时候想的一个算法——计算数组中最大和序列

本文与java语言无关，纯粹就是个解决问题的想法

问题：给定一个数组，要求求出数组中连续数和最大的索引对。比如，给定一个数组，里面有正数有负数和0。其中肯定有一个连续的序列（连续的，中间不能间断），比如说是索引3到索引5，这个序列的和是这个数组中连续序列中最大的，别的都没这个大。
{0,2.-1,9,7.6,-8,16}，这个数组中就是索引三到索引五这个连续序列的和最大。要求算法的时间复杂度问O(n)。

问题解决：如果时间复杂度要求是O(n³)或者是O(n平方)，就没意思了，直接循环搞定。

O(n)的时间复杂度如何解决：

注意，因为整个数组可能都是负数，这时候问题就退化成寻找数列中最大的负数了。首先，针对这种情况进行处理，将数组进行一次循环，找出第一个非负数索引和最后一个非负数索引，这个可以在一次循环中完成，如果 1）没找到，说明数组中全是负数，泽跳出循环，进行下一轮循环，寻找最大负数 2）如果两者相等，说明数组中只有一个正数，直接返回索引对 3）如果两者不等，则是相对复杂的情况，下面进行处理，到现在位置，时间复杂度是O(n)，因为之循环了一次。

1：将数组的第一个非负索引和最后一个非负索引之间的连续的正数和连续的负数相加。比如{0,2.-1,9,7.6,-8,16}，处理完后就应该得到数组{2, -1, 22, -8, 16}。这样整个数组就肯定是一个正负相间的数组。而且开头和结尾肯定是非负数。在进行处理的时候，还要维护一个大小是结果两倍的数组，用来存储每个元素的原来序列数值，比如，对于上面的数组，这个序列数组就应该是{0，1，2，2，3，5，6，6，7}，这个数组是数组index，其中0，1是第一个元素在原来数组中的序列，2，2 是第二个元素在原来数组中的序列，3，5是第三个元素在原数组中的序列，依此类推。本步骤的时间复杂度也是O(n)，没有循环嵌套，空间复杂度是O(2n)

2：现在得到一个正负相间的数组，而且数组中开头结尾都是非负数，而且数组中没个元素在原始数组中的索引序列对都是知道的。然后：
int start = 0;
int end = 0;
int count = 0;
对这个数组进行一次循环，循环中：
count += 数组[i]
if(count > 0){
将count的索引对(start, end)放入数组A中
将count的数值放入数组B中
} else{
count = 0;
}
这个循环时间复杂度是O(n)，空间复杂度O(2n)
循环结束后，要的结果就在数组A和数组B中，遍历数组B找到最大的元素，然后根据最大元素的索引去A中找出索引对，然后根据这个索引对去前面的数组index找出结果。时间复杂度O(n)


整个算法看下来，时间复杂度就是O(n)，进行了4次O(n)的循环，空间复杂度比较大一些，最大可能需要原来数组大小五倍的存储空间才能完成整个计算。