子数列和问题

一道经典的算法问题

# include<stdio.h>

int max(int A,int B, int C){

    return (A > B) ? (A > C ? A : C) : (B > C ? B : C);

}
// 改进版暴力搜索
int maxSubArray(int arr[],int n){
   
    int ultimate_max=0;
    for(int i=0;i<n;i++){
         int this_max=0;
        for(int j=i;j<n;j++){
            this_max += arr[j]; //直接加即可
            if(this_max>ultimate_max){
                ultimate_max=this_max;
            }
        }
    }
    return ultimate_max;
}

/*分治法球List[left]到List[right]的最大子列和，复杂度O(nlog2n)*/
int DivideAndConquer ( int List[], int left, int right ) {
    int MaxLeftSum, MaxRightSum;    //存放左右子问题的解。
    int MaxLeftBorderSum, MaxRightBorderSum;    //存放跨分界线的结果。
    
    int LeftBorderSum, RightBorderSum;
    int center, i;
    
    /*递归的终止条件，子列只有1个数字*/
    if ( left == right ) {
        if ( List[left] > 0 )    return List[left];
        else return 0;
    }
    
    /* “分”的过程 */
    center = ( left + right ) / 2;    //找到中分点。
    MaxLeftSum = DivideAndConquer ( List, left, center );    //递归求左子列和。
    MaxRightSum = DivideAndConquer ( List, center+1, right );    //递归求右子列和。
    
    /*求跨分界线的最大子列和*/
    MaxLeftBorderSum = 0;    LeftBorderSum = 0;
    for ( i = center; i >= left; i-- ) {
        LeftBorderSum += List[i];
        if ( LeftBorderSum > MaxLeftBorderSum )
            MaxLeftBorderSum = LeftBorderSum;
    }//左边扫描结束。
    
    MaxRightBorderSum = 0;    RightBorderSum = 0;
    for ( i = center+1; i <= right; i++ ) {
        RightBorderSum += List[i];
        if ( RightBorderSum > MaxRightBorderSum )
            MaxRightBorderSum = RightBorderSum;
    }//右边扫描结束。
    
    /*返回“治”的结果*/
    return max ( MaxLeftSum, MaxRightSum, MaxLeftBorderSum + MaxRightBorderSum );
}
/*此函数用于保持接口相同*/
int maxSubArray3 ( int List[], int N ) {
    return DivideAndConquer ( List, 0, N-1 );
}

//在线处理法
int maxSubArray2(int arr[],int n){
    int this_max=0;
    int ultimate_max=0;
    for(int i=0;i<n;i++){
        this_max += arr[i];
        if(this_max>ultimate_max){
            ultimate_max=this_max;
        }else if(this_max < 0){
            this_max = 0;
        }
    }
    return ultimate_max;
}

int main()
{
    int n=0;
    int array[1000];
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&array[i]);
    }
    printf("OK.");
    getchar();
    printf("%d",maxSubArray3(array,n));
}