[工学]数据结构经典题型.ppt

数据结构 杨旸 最大子序列问题 给定整数A1, A2, A3, A4..,An,求其中的最大子序列(为方便起见，如果所有整数为负数，则最大子序列为负数) 第一种算法 求出所有子序列的所有可能的组成，然后计算出最大子序列 int MaxSubsequenceSum (int A[ ], int N ) { int ThisSum, MaxSum, i, j, k; /* 1*/ MaxSum = 0; /* initialize the maximum sum */ /* 2*/ for( i = 0; i N; i++ ) /* start from A[ i ] */ /* 3*/ for( j = i; j N; j++ ) { /* end at A[ j ] */ /* 4*/ ThisSum = 0; /* 5*/ for( k = i; k = j; k++ ) /* 6*/ ThisSum += A[ k ]; /* sum from A[ i ] to A[ j ] */ /* 7*/ if ( ThisSum MaxSum ) /* 8*/ MaxSum = ThisSum; /* update max sum */ } /* end for-j and for-i */ /* 9*/ return MaxSum; } 第二种算法 减少了一个循环 int MaxSubsequenceSum (int A[ ], int N ) { int ThisSum, MaxSum, i, j; /* 1*/ MaxSum = 0; /* initialize the maximum sum */ /* 2*/ for( i = 0; i N; i++ ) { /* start from A[ i ] */ /* 3*/ ThisSum = 0; /* 4*/ for( j = i; j N; j++ ) { /* end at A[ j ] */ /* 5*/ ThisSum += A[ j ]; /* sum from A[ i ] to A[ j ] */ /* 6*/ if ( ThisSum MaxSum ) /* 7*/ MaxSum = ThisSum; /* update max sum */ } /* end for-j */ } /* end for-i */ /* 8*/ return MaxSum; } 第三种算法 利用分治思想递归之 我们的最大子序列可能出现在三处地方，或者前半部分，或者后半部分，或者跨越中部的部分 4 -3 5 -2 -1 2 6 -2 前半部分最大为6，后半部分为8，跨越中间的部分为6-2-1+8=11,因此中间为最大的子序列 Int MaxSubSum(int A[],int left,int right) { int MaxLeftSum, MaxRightSum; int MaxLeftBorderSum=0; int MaxRightBorderSum=0; int LeftBorderSum=0,RightBorderSum=0; int Center,i; if(Left==Right) if(A[Left]0) return A[Left]; else return 0; Center=(left+ right)/2; MaxLeftSum=MaxSubSum(A,left,Center); MaxRightSum=MaxSubSum(A, Center+1, right); for(i= Center;i=left;i--) //从中间往左边加 { LeftBorderSum+=A[i]; if(LeftBorderSumMaxLeftBorderSum) MaxLeftBorderSum=LeftBorderSum; } for(i= Center+1;i= right;i++)//从中间往后面加 { RightBorderSum+=A[i]; if(RightBorderSumMaxRightBorderSum) MaxRightBorderSum=RightBorderSum; } return Max3(MaxLeftSum, MaxRightSum, MaxLeftBorderSum+MaxR