//第一种
int MaxSubsequence1(const int A[], int N){
int Thissum, Maxsum=0;
int i, j, k;
for(i=0; i<N; i++){
for(j=i; j<N; j++){
Thissum = 0;
for(k=i; k<=j; k++){
Thissum += A[k];
}
if(Thissum>Maxsum){
Maxsum = Thissum;
}
}
}
return Maxsum;
}
//第二种
int MaxSubsequence2(const int A[], int N){
int Thissum, Maxsum=0;
int i, j;
for(i=0; i<N; i++){
Thissum = A[i];
for(j=i+1; j<N; j++){
if(Thissum>Maxsum){
Maxsum = Thissum;
}
Thissum += A[j];
}
}
return Maxsum;
}
//第三种
int Max3(int a, int b, int c){
int max;
if(a>b){
if(a>c){
max=a;
}
else{
max=c;
}
}
else{
if(b>c){
max=b;
}
else{
max=c;
}
}
return max;
}
int MaxSubsum(const int A[], int left, int right){
int MaxLeftSum=0, MaxRightSum=0;
int center, i;
if(left==right){
if(A[left]<0){
return 0;
}
else{
return A[left];
}
}
center = (right+left)/2;
MaxLeftSum = MaxSubsum(A, left, center);
MaxRightSum = MaxSubsum(A, center+1, right);
int MaxLeftBorderSum=0, MaxRightBorderSum=0;
int LeftBorderSum=0, RightBorderSum=0;
for(i=center; i>=left; i--){
LeftBorderSum += A[i];
if(LeftBorderSum>MaxLeftBorderSum){
MaxLeftBorderSum = LeftBorderSum;
}
}
for(i=center+1; i<=right; i++){
RightBorderSum += A[i];
if(RightBorderSum>MaxRightBorderSum){
MaxRightBorderSum = RightBorderSum;
}
}
return Max3(MaxLeftSum, MaxRightSum, MaxLeftBorderSum+MaxRightBorderSum);
}
int MaxSubsequence3(const int A[], int N){
return MaxSubsum(A, 0, N-1);
}
//第四种
int MaxSubsequence4(const int A[], int N){
int Thissum=0, Maxsum=0;
int i;
for(i=0; i<N; i++){
Thissum += A[i];
if(Thissum>Maxsum){
Maxsum=Thissum;
}
else if(Thissum<0){
Thissum = 0;
}
}
return Maxsum;
}
来源: http://www.bubuko.com/infodetail-1968721.html