算法题：最大连续子序列和

  求取数组中最大连续子序列和，例如给定数组为 $A=\{1， 3， -2， 4， -5\}$， 则最大连续子序列和为 6，即 $1+3+(-2)+ 4 = 6$。

题解

最大连续子序列和：当前元素前面为正数，带上前面的序列；前面为负数或 0，自己为起点。

  因为最大连续子序列和只可能是以位置 $0 \sim n-1$ 中某个位置结尾。当遍历到第 $i$ 个元素时，判断在它前面的连续子序列和是否大于 0，如果大于 0，则以位置 $i$ 结尾的最大连续子序列和为元素 $i$ 和前面的连续子序列和相加；否则，则以位置 $i$ 结尾的最大连续子序列和为元素 $i$。

int maxSequence(int a[], int len) {
    int maxSum, maxHere;
    maxSum = maxHere = a[0];   // 初始化最大和为 a[0]
    for (int i = 1; i < len; ++i) {
        if (maxHere <= 0)
            maxHere = a[i];  // 如果前面位置最大连续子序列和小于等于 0，则以当前位置 i 结尾的最大连续子序列和为 a[i]
        else
            maxHere += a[i]; // 如果前面位置最大连续子序列和大于 0，则以当前位置 i 结尾的最大连续子序列和为它们两者之和
        if (maxHere > maxSum) {
            maxSum = maxHere;  // 更新最大连续子序列和
        }
    }
    return maxSum;
}

时间复杂度：$O(n)$ 。

打赏