浙江大学《数据结构》MOOC 编程练习 题解（一）
01-复杂度1 最大子列和问题
给定K个整数组成的序列{ N1, N2, ..., NK }，“连续子列”被定义为{ Ni, Ni+1, ..., Nj }，其中 1 <= i <= j <= K。“最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列{ -2, 11, -4, 13, -5, -2 }，其连续子列{ 11, -4, 13 }有最大的和20。现要求你编写程序，计算给定整数序列的最大子列和。
本题旨在测试各种不同的算法在各种数据情况下的表现。各组测试数据特点如下：
数据1：与样例等价，测试基本正确性；
数据2：100个随机整数；
数据3：1000个随机整数；
数据4：10000个随机整数；
数据5：100000个随机整数；
输入格式：
输入第1行给出正整数K (<= 100000)；第2行给出K个整数，其间以空格分隔。
输出格式：
在一行中输出最大子列和。如果序列中所有整数皆为负数，则输出0。
输入样例：
6
-2 11 -4 13 -5 -2
输出样例：
20
代码长度限制：16 KB
时间限制：50000 ms
内存限制：64 MB
本题一共有四种算法：
第一种算法：
int MaxSubseqSum1(int A[], int N) {
int thisSum, maxSum = 0;
int i, j, k;
for (i = 0; i < N; i++) { /* i是子列左端位置 */
for (j = i; j < N; j++) { /* j是子列右端位置 */
thisSum = 0; /* thisSum是从A[i]到A[j]的子列和 */
for (k = i; k <= j; k++) {
thisSum += A[k];
}
if (thisSum > maxSum) { /* 如果刚得到的这个子列和更大 */
maxSum = thisSum; /* 则更新结果 */
}
} /* j循环结束 */
} /* i循环结束 */
return maxSum;
}
从时间复杂度进行分析，该算法使用了3个循环，最高次为3，所以我们就记作T(N)=O(N3)，本题测试数据中最高次有100000个数据，而100000 ^ 3 = 10 ^ 15，如果每秒计算1亿次，也要116天左右才能运行出来。所以该算法效率不行。
算法2：
int MaxSubseqSum2(int A[], int N) {
int thisSum, maxSum = 0;
int i, j;
for (i = 0; i < N; i++) { /* i是子列左端位置 */
thisSum = 0; /* thisSum是从A[i]到A[j]的子列和 */
for (j = i; j < N; j++) { /* j是子列右端位置 */
thisSum += A[j];
/* 对于相同的i，不同的j，只要在j – 1次循环的基础上累加1项即可 */
if (thisSum > maxSum) { /* 如果刚得到的这个子列和更大 */
maxSum = thisSum; /* 则更新结果 */
}
} /* j循环结束 */
} /* i循环结束 */
return maxSum;
}
从时间复杂度进行分析，该算法使用了2个循环，最高次为2，比算法1要好很多，但是当100000个数据的时候，需要大约100秒的时间，也会超时。效率还是比较低。
算法3：
int Max3(int A, int B, int C) {
return A > B ? A > C ? A : C : B > C ? B : C;
}
int DivideAndConquer(int List[], int left, int right) {
/* 分治法求List[left]到List[right]的最大子列和 */
int maxLeftSum, maxRightSum; /* 存放左右子问题的解 */
int maxLeftBorderSum, maxRightBorderSum; /*存放跨分界线的结果*/
int leftBorderSum, rightBorderSum;
int center, i;
if (left == right) { /* 递归的终止条件，子列只有1个数字 */
if(List[left] > 0) {
return List[left];
} else {
return 0;
}
}
/* 下面是"分"的过程 */
center = (left + right) / 2; /* 找到中分点 */
/* 递归求得两边子列的最大和 */
maxLeftSum = DivideAndConquer(List, left, center);
maxRightSum = DivideAndConquer(List, center + 1, right);
/* 下面求跨分界线的最大子列和 */
maxLeftBorderSum = 0; leftBorderSum = 0;
for (i = center; i >= left; i--) { /* 从中线向左扫描 */
leftBorderSum += List[i];
if(leftBorderSum > maxLeftBorderSum) {
maxLeftBorderSum = leftBorderSum;
}
} /* 左边扫描结束 */
maxRightBorderSum = 0; rightBorderSum = 0;
for (i = center + 1; i <= right; i++) { /* 从中线向右扫描 */
rightBorderSum += List[i];
if (rightBorderSum > maxRightBorderSum) {
maxRightBorderSum = rightBorderSum;
}
} /* 右边扫描结束 */
/* 下面返回"治"的结果 */
return Max3(MaxLeftSum, MaxRightSum, MaxLeftBorderSum + MaxRightBorderSum);
}
int MaxSubseqSum3(int List[], int N) {
return DivideAndConquer(List, 0, N-1);
}
该算法又叫做分而治之，就是将问题化成小块，在小块里进行解决，然后再放回到大块，这也可以说是递归的一种吧，在课上，陈越老师也讲过，该算法的复杂度为T(n) = O(nlogn)，取100000时，在每秒一亿次运算的基础上，可以在大约0.02秒内得到答案，但是PINTIA上面的计算机没那么大本事，而且这代码量太长，这条先备用。
算法4（推荐）：在线处理
int MaxSubseqSum4(int A[], int N) {
int thisSum, maxSum;
int i;
thisSum = maxSum = 0;
for (i = 0; i < N; i++) {
thisSum += A[i];
if (thisSum > maxSum) {
maxSum = thisSum;
} else if (thisSum < 0) {
thisSum = 0;
}
}
return maxSum;
}
该算法的时间复杂度为O(N)，因为只执行了一次循环，当N取100000时，结果也是很快就能出来。
该题完整的AC代码：
C：
#include <stdio.h>
int MaxSubseqSum(int A[], int N) {
int thisSum, maxSum;
int i;
thisSum = maxSum = 0;
for (i = 0; i < N; i++) {
thisSum += A[i];
if (thisSum > maxSum) {
maxSum = thisSum;
} else if (thisSum < 0) {
thisSum = 0;
}
}
return maxSum;
}
int main() {
int n, i;
scanf("%d", &n);
int a[n];
for (i = 0; i < n; i++) {
scanf("%lld", &a[i]);
}
printf("%d\n", MaxSubseqSum(a, n));
return 0;
}
Python:
def MaxSubseqSum(a, n):
thisSum, maxSum = 0, 0
for i in range(n):
thisSum += a[i]
if thisSum > maxSum:
maxSum = thisSum
elif thisSum < 0:
thisSum = 0
return maxSum
n = eval(input())
a = list(map(int, input().split(" ")))
print(MaxSubseqSum(a, n))
本来试着用Java写的，但是Java太废内存了，还废时间：
// Memory Limit Exceeded
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
int n, i;
Scanner javain = new Scanner(System.in);
n = javain.nextInt();
int a[] = new int[n + 1];
for (i = 0; i < n; i++) {
a[i] = javain.nextInt();
}
System.out.println(MaxSubseqSum(a, n));
}
public static int MaxSubseqSum(int A[], int N) {
int thisSum, maxSum;
int i;
thisSum = maxSum = 0;
for (i = 0; i < N; i++) {
thisSum += A[i];
if (thisSum > maxSum) {
maxSum = thisSum;
} else if (thisSum < 0) {
thisSum = 0;
}
}
return maxSum;
}
}
