征求更好的答案

alexlee002

题目：
给定K个整数序列{N1, N2,...NK}, 其任意连续子序列 {Ni, Ni+1,.... Nj}(i <=i<=j<=k);最大连续子序列是所有连续子序列里边所有元素和最大的那个， 如序列{-2， 11， -4， 13，-5， -2}， 最大连续子序列为{11, -4, 13}, 最大和20，

要求：
给定一个序列，求出其最大和， 并且输出该最大子序列第一个和最后一个元素， 如最大子序列不唯一， 则输出， i和j最小的那个，如k个元素都是负数， 则最大和为0， 输出整个序列首尾元素。

要求给出算法的时间复杂度为O(N), 空间复杂度要最小。


各位有什么好的算法能达到时间/空间复杂度要求的？

pointer

换个符号吧:

设给定的n个数为a_1,a_2,...,a_n.
定义S_k=a_1+a_2+...+a_k.
从前向后计算S_k,
并且记录S_1,...,S_k中的最小者,
计算S_k与此最小值的差, 记录这个差的最大者,以及对应的两个脚标.

这个算法就应满足要求.

alexlee002

[QUOTE

从前向后计算S_k,
QUOTE]

这里的复杂度就是O(N^2)了， 没有满足要求

pointer

to alexlee002:
是累加计算啊, 每次在前面的结果加上新的值就行, 不用保存S_k的值.