浙江大學(xué)《數(shù)據(jù)結(jié)構(gòu)》MOOC 編程練習(xí) 題解（一）
01-復(fù)雜度1 最大子列和問(wèn)題
給定K個(gè)整數(shù)組成的序列{ N1, N2, ..., NK }，“連續(xù)子列”被定義為{ Ni, Ni+1, ..., Nj }，其中 1 <= i <= j <= K。“最大子列和”則被定義為所有連續(xù)子列元素的和中最大者。例如給定序列{ -2, 11, -4, 13, -5, -2 }，其連續(xù)子列{ 11, -4, 13 }有最大的和20?，F(xiàn)要求你編寫(xiě)程序，計(jì)算給定整數(shù)序列的最大子列和。
?
本題旨在測(cè)試各種不同的算法在各種數(shù)據(jù)情況下的表現(xiàn)。各組測(cè)試數(shù)據(jù)特點(diǎn)如下：
?
數(shù)據(jù)1：與樣例等價(jià)，測(cè)試基本正確性；
數(shù)據(jù)2：100個(gè)隨機(jī)整數(shù)；
數(shù)據(jù)3：1000個(gè)隨機(jī)整數(shù)；
數(shù)據(jù)4：10000個(gè)隨機(jī)整數(shù)；
數(shù)據(jù)5：100000個(gè)隨機(jī)整數(shù)；
?
輸入格式：
輸入第1行給出正整數(shù)K (<= 100000)；第2行給出K個(gè)整數(shù)，其間以空格分隔。
?
輸出格式：
在一行中輸出最大子列和。如果序列中所有整數(shù)皆為負(fù)數(shù)，則輸出0。
?
輸入樣例：
6
-2 11 -4 13 -5 -2
?
輸出樣例：
20
?
代碼長(zhǎng)度限制：16 KB
時(shí)間限制：50000 ms
內(nèi)存限制：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) {? /* 如果剛得到的這個(gè)子列和更大 */
??????????????? maxSum = thisSum; ?/* 則更新結(jié)果 */
??????????? }
??????? } ?/* j循環(huán)結(jié)束 */
??? } ?/* i循環(huán)結(jié)束 */
??? return maxSum;
}
?
從時(shí)間復(fù)雜度進(jìn)行分析，該算法使用了3個(gè)循環(huán)，最高次為3，所以我們就記作T(N)=O(N3)，本題測(cè)試數(shù)據(jù)中最高次有100000個(gè)數(shù)據(jù)，而100000 ^ 3 = 10 ^ 15，如果每秒計(jì)算1億次，也要116天左右才能運(yùn)行出來(lái)。所以該算法效率不行。
?
算法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];
??????????? /* 對(duì)于相同的i，不同的j，只要在j – 1次循環(huán)的基礎(chǔ)上累加1項(xiàng)即可 */
??????????? if (thisSum > maxSum) {? /* 如果剛得到的這個(gè)子列和更大 */
??????????????? maxSum = thisSum; ?/* 則更新結(jié)果 */
??????????? }
??????? } ?/* j循環(huán)結(jié)束 */
??? } ?/* i循環(huán)結(jié)束 */
??? return maxSum;
}
?
從時(shí)間復(fù)雜度進(jìn)行分析，該算法使用了2個(gè)循環(huán)，最高次為2，比算法1要好很多，但是當(dāng)100000個(gè)數(shù)據(jù)的時(shí)候，需要大約100秒的時(shí)間，也會(huì)超時(shí)。效率還是比較低。
?
算法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;? /* 存放左右子問(wèn)題的解 */
??? int maxLeftBorderSum, maxRightBorderSum;? /*存放跨分界線的結(jié)果*/
??? int leftBorderSum, rightBorderSum;
??? int center, i;
??? if (left == right) {? /* 遞歸的終止條件，子列只有1個(gè)數(shù)字 */
??????? if(List[left] > 0) {
??????? ?????? return List[left];
????????????? } else {
???????????????????? return 0;
????????????? }
??? }
?
??? /* 下面是"分"的過(guò)程 */
??? center = (left + right) / 2; /* 找到中分點(diǎn) */
??? /* 遞歸求得兩邊子列的最大和 */
??? 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;
? ? ? ? }
??? }? /* 左邊掃描結(jié)束 */
?
??? maxRightBorderSum = 0; rightBorderSum = 0;
??? for (i = center + 1; i <= right; i++) {? /* 從中線向右掃描 */
??????? rightBorderSum += List[i];
??????? if (rightBorderSum > maxRightBorderSum) {
? ? ? ? ? ? maxRightBorderSum = rightBorderSum;
? ? ? ? }
??? }? /* 右邊掃描結(jié)束 */
?
??? /* 下面返回"治"的結(jié)果 */
? ? return Max3(MaxLeftSum, MaxRightSum, MaxLeftBorderSum + MaxRightBorderSum);
}
?
int MaxSubseqSum3(int List[], int N) {
??? return DivideAndConquer(List, 0, N-1);
}
?
該算法又叫做分而治之，就是將問(wèn)題化成小塊，在小塊里進(jìn)行解決，然后再放回到大塊，這也可以說(shuō)是遞歸的一種吧，在課上，陳越老師也講過(guò)，該算法的復(fù)雜度為T(mén)(n) = O(nlogn)，取100000時(shí)，在每秒一億次運(yùn)算的基礎(chǔ)上，可以在大約0.02秒內(nèi)得到答案，但是PINTIA上面的計(jì)算機(jī)沒(méi)那么大本事，而且這代碼量太長(zhǎng)，這條先備用。
?
算法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;
}
?
該算法的時(shí)間復(fù)雜度為O(N)，因?yàn)橹粓?zhí)行了一次循環(huán)，當(dāng)N取100000時(shí)，結(jié)果也是很快就能出來(lái)。
該題完整的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))
本來(lái)試著用Java寫(xiě)的，但是Java太廢內(nèi)存了，還廢時(shí)間：
// 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;
? ? }
}
