最大连续子数列

在线处理法在线处理法


#include < stdio.h>
int main()
{
    int arry[11];
    int x, Maxsum = 0, Thissum = 0;
    for (x = 0; x <= 10; x++)
    {
        scanf("%d", &arry[x]);
        Thissum += arry[x];
        if (Thissum > Maxsum)Maxsum = Thissum;
        else if 
            (Thissum < 0)Thissum = 0;
    }
    printf("%d", Maxsum);
    return 0;
}

从左往右开始扫描，若现在的Thissum为负数就丢弃，比较大就替代。

分而治之的递归算法

 
#include< stdio.h>
int Maxs(int x, int y, int z)
{
    return x > y ? x > z ? x : z : y > z ?  y : z;
}
int Maxsum(int left, int right, int arry[])
{
    if (left == right)
        if (arry[right] < 0)return 0;
        else return arry[right];//从最小的单个数才开始计算
    int rightsum = 0, leftsum = 0, center = (left + right) / 2;
    int sum = 0,maxsumright=0,maxsumleft=0;
    //需要比较中间线左边的最大和右边的最大以及横跨中间线的最大
    rightsum = Maxsum(center+1, right, arry);
    leftsum = Maxsum(left, center, arry);
    int i;
    for (i = center; i >= left; i--)
    {
        sum += arry[i];
        if (sum > maxsumleft)maxsumleft = sum;
    }//先计算从中间线开始左边的最大值
    sum = 0;
    for (i = center + 1; i <= right; i++)
    {
        sum += arry[i];
        if (sum > maxsumright)maxsumright = sum;
    }//再计算右边最大值注意是连续的
    return Maxs(leftsum, rightsum, maxsumleft + maxsumright);
}
int main()
{
    int arry[101];
    int i, j;
    scanf("%d", &j);
    for (i = 0; i <= j-1; i++)
    {
        scanf("%d", &arry[i]);
    }
    printf("%d", Maxsum(0, j - 1, arry));
    return 0;
}
大概流程
大概流程