求解最大连续子序列和问题

方法一

//求解最大连续子序列和问题
#include<stdio.h>
long maxSubSum(int a[],int n){
	int i,j,k;
	long maxSum=a[0],thisSum;
	for(i=0;i<n;i++){
		for(j=i;j<n;j++){
			thisSum=0;
			for(k=0;k<j;k++)
				thisSum += a[k];
			if(thisSum > maxSum)
				maxSum = thisSum;
		}
	}
}
int main(){
	int a[] = {-2,11,-4,13,-5,-2},n=6;
	printf("a序列的最大连续子序列的和:%d",maxSubSum(a,n));	
} 

方法二

#include<stdio.h>
int maxSubSum(int a[],int n){
	int i,j;
	long maxSum=a[0],thisSum;
	for(i=0;i<n;i++){
		thisSum=0;
		for(j=i;j<n;j++){
			thisSum += a[j];
			if(thisSum > maxSum)
				maxSum = thisSum;
		}
	}
}
int main(){
	int a[] = {-2,11,-4,13,-5,-2},n=6;
	printf("a序列的最大连续子序列的和:%d",maxSubSum(a,n));	
} 

　　方法三

#include<stdio.h>
int maxSubSum(int a[],int n){
	int i,maxSum=0,thisSum=0;
	for(i=0;i<n;i++){
		thisSum += a[i];
		if(thisSum < 0)
			thisSum = 0;
		if(maxSum < thisSum)
			maxSum = thisSum;
	}
} 
int main(){
	int a[] = {-2,11,-4,13,-5,-2},n=6;
	printf("a序列的最大连续子序列的和:%d",maxSubSum(a,n));	
} 

　　分治法

　　动态规划

//动态规划
#include<stdio.h>
#define MaxN 20
void maxSubSum(int a[],int b[],int n){    //求b数组 
    int j;
    b[0] = 0;
    for(j=1;j<=n;j++){
        if(b[j-1] + a[j] > a[j])
            b[j] = b[j-1] + a[j];
        else
            b[j] = a[j]; 
    } 
}
void disp(int a[],int b[],int n){
    int maxj,i,j,k;
    maxj = 1;
    for(j=2;j<=n;j++)
        if(b[j] > b[maxj])    maxj = j;
    for(k = maxj;k>=1;k--)
        if(b[k] <= 0)    break;
    printf("最大连续子序列和:%d
",b[maxj]);
    printf("所选子序列:");
    for(i = k+1;i<=maxj;i++)
        printf("%d ",a[i]);
    printf("
"); 
}
int main(){
    int a[] = {0,-2,11,-4,13,-5,-2},n=6;
    int b[MaxN];
    maxSubSum(a,b,n);
    disp(a,b,n);
    return 0;
}