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.

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

具体实现如下：

#include 
  
   
#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;
}
  

结果是意料之中的超时

接下来我们再换一个效率高点的算法。其实上一个算法中第三层fZ http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vctGtu7e/ydLUyKW19KOsyMO12rb+suOx7cq+0tRhcnJbaV3OqsbwteO1xNfT0PLB0KOsvs3V4tH50rvWsc/y09K808/CyKWjrMjnufu6zbTz09ptYXhTdW0sxMfDtL7NuPzQwiYjMjA1NDA7oaPKtc/WyOfPwqO6PC9oMj4KPHByZSBjbGFzcz0="brush:java;">#include #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 
    
     
#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次左右才改对，不过把数组开销都省了，真心够精简的。

#