Question

连续子序列什么意思?什么是连续子序列?最大连续子序列又是什么?

例如给定序列{ -2, 11, -4, 13, -5, -2 }，其最大连续子序列为{11,-4,13}，最大连续子序列和即为20。
问 : 为什么最大连续子序列为{11,-4,13}???
我想知道的是这些名词的定义是什么?什么意思?而不是怎么算!!!

Answer 1

这个最大连续子序列是这个意思：
例如从-2开始计算，{-2，11}、{-2，11，-4}...{-2，11，-4，13，-5，-2}这些都是其子序列（包含其自身）；
如果从11开始计算，{11，-4}、{11，-4，13}...{11，-4，13，-5，-2}这些都是其子序列；、
类推：一直到-5开头的{-5，-2}，这么多都是给定序列的子序列；
而最大连续子序列就是要在这里面寻找相加和最大的子序列，可以用暴力枚举，也可以用分治来解，也可以用动态规划来求解。

Answer 2

设原数组为a，遍历数组，建立和数列S：S[0]=0，S[i]=S[i-1]+a[i]。同时S[i]的内容还记录i。然后对S进行稳定排序。现在S可以分成很多段，每段的数都相同，所求最长连续子数组的第一个数的下标和最后一个数的下边必分别为其中一段第一个数的i与最后一个数的i，算出每段第一个数的i与最后一个数的i的差，取最大的那个即可。

Answer 3

最大连续子序列应该就是这个连续序列的和最大，{11,-4,13}这个子序列的和最大