《数据结构与算法》Day.1 最大子列和

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);