给定一个整数数列A1,A2,,…,An,求∑ A(k) ( k from i to j ,0 <= i <= j <= n )的最大值。规定,当所有整数均为负数,则结果为0。
以下共四种代码,时间复杂度由高到低。
O( N^3 )代码,枚举所有的子序列
1 2 3 4 5 6 7 8 9 10 11 12
intMaxSubsequenceSum( constint A[], int N){ int tempSum, MaxSum = 0, i, j, k; for ( i = 0 ; i < N ; i++ ) for ( j = 0 ; j < N ; j++ ){ tempSum = 0; for ( k = i ; k < j ; k++ ) tempSum += A[k]; if ( tempSum > MaxSum ) MaxSum = tempSum; } return MaxSum; }
O( N^2 )代码,由∑(i->j) = ∑(i->j-1) + Aj 可简化上述代码一层循环
1 2 3 4 5 6 7 8 9 10 11 12
intMaxSubsequenceSum( constint A[], int N){ int tempSum, MaxSum = 0, i, j; for ( i = 0 ; i < N ; i++ ){ tempSum = 0; for ( j = i ; j < N ; j++ ){ tempSum += A[j]; if ( tempSum > MaxSum ) MaxSum = tempSum; } } return MaxSum; }
staticMAX3( int a, int b, int c ){ a = a > b ? a : b ; return a > c ? a : c ; } staticintPartition( constint A[], int l, int r){ if ( l == r ) // Only one number if ( A[l] > 0 ) return A[l]; else return0; int MaxL, MaxR; int MaxLBorder = 0 , MaxRBorder = 0 , tempLBorder = 0 , tempRBorder = 0; int mid = ( l + r ) >> 1, i; MaxL = Partition( A, l, mid ); MaxR = Partition( A, mid + 1, r ); for ( i = mid ; i >= l ; i-- ){ tempLBorder += A[i]; if ( tempLBorder > MaxLBorder ) MaxLBorder = tempLBorder; } for ( i = mid + 1 ; i <= r ; i++ ){ tempRBorder += A[i]; if ( tempRBorder > MaxRBorder ) MaxRBorder = tempRBorder; } return MAX3( MaxL , MaxR , MaxLBorder + MaxRBorder ); } intMaxSubsequence( constint A[], int N ){ return Partition( A , 0 , N - 1 ); }
O( N ) 代码,正确性容易理解。以上三份代码均为离线算法,此代码满足联机特性(不需要记忆数据,顺序读入的同时处理数据)。
1 2 3 4 5 6 7 8 9 10 11
intMaxSubsequenceSum( constint A[], int N ){ int tempSum = 0, MaxSum = 0, i; for ( i = 0 ; i < N ; i++ ){ tempSum += A[i]; if ( tempSum > MaxSum ) MaxSum = tempSum; elseif ( tempSum < 0 ) tempSum = 0; } return MaxSum; }
单向链表的类型声明及其ADT操作
类型声明(模拟整型数组)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
typedefstruct Node{ int value; struct Node* next; }Node;
#ifndef _List_ Node * MakeEmpty( Node * L ); Node * Find( int toFind, Node * L ); Node * FindPrevious( int present, Node * L ); Node * head; // need to malloc intIsEmpty( Node * L ); intIsLast( Node * present, Node * L ); voidInsert( int x, Node * L, Node * insertP ); voidDelete( int x, Node * L ); voidDeleteList( Node * L );
Node * Find( int toFind, Node * L ){ Node * P = L->next; while ( P != NULL && P->value != toFind ) /* 1 */ P = P->next; return P; /* 1. if P == NULL, then the check after && won't run */ }
Node * FindPrevious( int present, Node * L ){ Node * P = L; while ( P->next != NULL && P->next->value != toFind ) /* 1 */ P = P->next; return P; }