HDU1003 Max Sum 最大子序列和的问题【四种算法分析+实现】

本文主要是介绍HDU1003 Max Sum 最大子序列和的问题【四种算法分析+实现】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

就拿杭电OJ上的第1003题开始吧，这题比原书要复杂一些。

Problem Description
Given a sequence a[1],a[2],a[3]......a[n], your job is to calculate the max sum of a sub-sequence. For example, given (6,-1,5,4,-7), the max sum in this sequence is 6 + (-1) + 5 + 4 = 14.

Input
The first line of the input contains an integer T(1<=T<=20) which means the number of test cases. Then T lines follow, each line starts with a number N(1<=N<=100000), then N integers followed(all the integers are between -1000 and 1000).

Output
For each test case, you should output two lines. The first line is "Case #:", # means the number of the test case. The second line contains three integers, the Max Sum in the sequence, the start position of the sub-sequence, the end position of the sub-sequence. If there are more than one result, output the first one. Output a blank line between two cases.

Sample Input
2
5 6 -1 5 4 -7
7 0 6 -1 1 -6 7 -5

Sample Output
Case 1:
14 1 4
Case 2:
7 1 6

题意很简单，那么就开始分析了，最容易想到的方法自然是枚举，只需要枚举出所有的可能情况。

具体实现如下：

#include <stdio.h>
#define maxn 100000 + 2
int arr[maxn];int main(){int t, n, maxLeft, maxRight, maxSum, id = 1;int thisSum;scanf("%d", &t);while(t--){scanf("%d", &n);for(int i = 0; i < n; ++i)scanf("%d", &arr[i]);maxSum = arr[0];maxLeft = maxRight = 0;/*maxSubsequenceSum------O(N^3)*/for(int i = 0; i < n; ++i){for(int j = i; j < n; ++j){thisSum = 0;for(int k = i; k <= j; ++k){thisSum += arr[k];}if(thisSum > maxSum){maxSum = thisSum;maxLeft = i; maxRight = j;}}}printf("Case %d:\n%d %d %d\n", id++, maxSum, maxLeft + 1, maxRight + 1);if(t) printf("\n");}return 0;
}

结果是意料之中的超时

接下来我们再换一个效率高点的算法。其实上一个算法中第三层for循环可以去掉，让第二层表示以arr[i]为起点的子序列，就这样一直向右加下去，如果和大于maxSum,那么就更新值。实现如下：

#include <stdio.h>
#define maxn 100000 + 2
int arr[maxn]; int main(){int t, n, maxLeft, maxRight, maxSum, id = 1;int thisSum;scanf("%d", &t);while(t--){scanf("%d", &n);for(int i = 0; i < n; ++i)scanf("%d", &arr[i]);maxSum = arr[0];maxLeft = maxRight = 0;/*maxSubsequenceSum------O(N^2)*/for(int i = 0; i < n; ++i){thisSum = 0;for(int j = i; j < n; ++j){thisSum += arr[j];if(thisSum > maxSum){maxSum = thisSum;maxLeft = i;maxRight = j;}				}}printf("Case %d:\n%d %d %d\n", id++, maxSum, maxLeft + 1, maxRight + 1);if(t) printf("\n");}return 0;
}

依旧超时

只能再换效率更高算法，对于最大子序列和这个问题其实可以细分成多个子问题来求解，再将子问题的解合并，于是可以考虑下分治法，具体实现如下：

#include <stdio.h>
#define maxn 100000 + 2
int arr[maxn]; 
int t, n, maxLeft, maxRight, maxSum, id = 1;int max3(int a, int b, int c){if(a >= b && a >= c) return 1;if(b >= a && b >= c) return 2;if(c >= a && c >= b) return 3;
}int maxSubsequenceSum(int left, int right, int *l, int *r){int thisLeft, thisRight;int leftSum, rightSum, midSum, mid;int leftBorderSum, maxLeftBorderSum;int rightBorderSum, maxRightBorderSum;int ll, lr, rl, rr, ml, mr;if(left == right){*l = *r = left;return arr[left];}mid = (left + right) / 2;leftSum = maxSubsequenceSum(left, mid, &ll, &lr);rightSum = maxSubsequenceSum(mid + 1, right, &rl, &rr);leftBorderSum = 0; thisLeft = mid;maxLeftBorderSum = arr[mid];for(int i = mid; i >= left; --i){leftBorderSum += arr[i];if(leftBorderSum >= maxLeftBorderSum){maxLeftBorderSum = leftBorderSum;thisLeft = i;}}rightBorderSum = 0; thisRight = mid + 1;maxRightBorderSum = arr[mid + 1];for(int i = mid + 1; i <= right; ++i){rightBorderSum += arr[i];if(rightBorderSum > maxRightBorderSum){maxRightBorderSum = rightBorderSum;thisRight = i;}}midSum = maxLeftBorderSum + maxRightBorderSum;   int sign = max3(leftSum, midSum, rightSum);if(sign == 1){maxSum = leftSum;*l = ll;*r = lr;}else if(sign == 2){maxSum = midSum;*l = thisLeft;*r = thisRight;}else{maxSum = rightSum;*l = rl;*r = rr;}return maxSum;
}int main(){    scanf("%d", &t);while(t--){scanf("%d", &n);for(int i = 0; i < n; ++i)scanf("%d", &arr[i]);maxSum = arr[0];maxLeft = maxRight = 0;maxSubsequenceSum(0, n - 1, &maxLeft, &maxRight);printf("Case %d:\n%d %d %d\n", id++, maxSum, maxLeft + 1, maxRight + 1);if(t) printf("\n");}return 0;
}

终于AC了！

书上还介绍了一个狂拽酷炫叼炸天的O(n)算法，这里也尝试一下，再对比一下与分治法的时间消耗。改的过程真是相当得不顺利，WA了5次左右才改对，不过把数组开销都省了，真心够精简的。

#include <stdio.h>int main(){int t, n, maxLeft, maxRight, maxSum, temp;int thisLeft, thisSum;scanf("%d", &t);for(int id = 1; id <= t; ++id){scanf("%d", &n);scanf("%d", &maxSum);thisLeft = maxLeft = maxRight =  0;thisSum = maxSum;if(thisSum < 0){ thisSum = 0; thisLeft = 1; }for(int i = 1; i < n; ++i){scanf("%d", &temp);thisSum += temp;if(thisSum > maxSum){maxSum = thisSum;maxLeft = thisLeft;maxRight = i;}if(thisSum < 0){thisLeft = i + 1;thisSum = 0;}}printf("Case %d:\n%d %d %d\n", id, maxSum, maxLeft + 1, maxRight + 1);if(id != t) printf("\n");}return 0;
}