int MaxSubseqSum1(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;
} // T(N) = O(N^3)
int MaxSubseqSum2(int A[], int N) {
int ThisSum, MaxSum = 0;
int i, j, k;
for( i = 0; i < N; i++) {
ThisSum = 0;
for( j = i; j < N; j++) {
ThisSum += A[j];
if( ThisSum > MaxSum)
MaxSum = ThisSum;
}
}
return MaxSum;
} // T(N) = O(N^2)
//返回3个整数中的最大的一个
int getmaxint3(int a,int b,int c) {
return a>b?(a>c?a:c):(b>c?b:c);
}
//递归调用分治思想的核心代码
int MaxSubseqSum3(int nums[],int left,int right) {
//左右最大子列和
int MaxLeftSum, MaxRightSum;
//跨边界左右最大子列和
int MaxLeftBorderSum, MaxRightBorderSum;
//当前计算的左右边界子列和
int LeftBorderSum, RightBorderSum;
int center, i;
//递归调用终止条件,子列只有一个元素
if( left == right ) {
if( nums[left] > 0 ) return nums[left];
else return 0;
}
//先分
center = ( left + right ) / 2;
//递归调用获取左边最大子列和 left.....center
MaxLeftSum = MaxSubseqSum3( nums, left, center );
//递归调用获取右边最大子列和 center+1.....right
MaxRightSum = MaxSubseqSum3( nums, center+1, right );
//跨边界最大子列和
MaxLeftBorderSum = 0;
LeftBorderSum = 0;
for( i=center; i>=left; i-- ) { /* 从中线向左扫描 */
LeftBorderSum += nums[i];
if( LeftBorderSum > MaxLeftBorderSum )
MaxLeftBorderSum = LeftBorderSum;
} /* 左边扫描结束 */
MaxRightBorderSum = 0;
RightBorderSum = 0;
for( i=center+1; i<=right; i++ ) { /* 从中线向右扫描 */
RightBorderSum += nums[i];
if( RightBorderSum > MaxRightBorderSum )
MaxRightBorderSum = RightBorderSum;
} /* 右边扫描结束 */
/* 下面返回"治"的结果 */
return getmaxint3( MaxLeftSum, MaxRightSum, MaxLeftBorderSum + MaxRightBorderSum );
}
int MaxSubseqSum4(int A[], int N) {
int ThisSum, MaxSum;
int i;
ThisSum = MaxSum = 0;
for( i = 0; i < N; i++) {
ThisSum += A[i];
if( ThisSum > MaxSum)
MaxSum = ThisSum;
else if(ThisSum < 0)
ThisSum = 0;
}
return MaxSum;
} //T(N) = O(N);
———————————————— 版权声明:本文为博主「Sofar」的原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接及本声明。 原文链接:https://sofar1994.github.io/post/19111/