明天试试分治法，分治的话代码可能要难写一些
原题

#include<stdio.h>

int Compare(int CurArraySum,int MaxArraySum)
{
    if( CurArraySum > MaxArraySum )
        MaxArraySum=CurArraySum;

    return MaxArraySum;
}

int main()
{
    int Array[100000];
    int CurArraySum,MaxArraySum;
    int k,i;
    int book; //记录Array[]中负数的个数

    book=0;
    CurArraySum=0;
    MaxArraySum=-9999999;

    scanf("%d",&k);

    for(i=0;i<k;i++)
    {
        scanf("%d",&Array[i]);
    }

    //在线处理，扫描下一个数与最大和比较，当前和为负数则不将当前和记录至下一个数，重置后扫描
    for(i=0;i<k;i++)
    {
        if(Array[i]<0) book++; 

        if( CurArraySum<0 )
        {
            CurArraySum=0;
            CurArraySum+=Array[i];//重新扫描
            MaxArraySum = Compare( CurArraySum , MaxArraySum );
        }
        else 
        {
            CurArraySum+=Array[i];//虽然第一项为负数时会将其包含进CurArraySum，但是后会被重置为0，即使只有一项由于book的记录也会输出0
            MaxArraySum = Compare( CurArraySum , MaxArraySum );
        }
    }

    if(book==k)
        printf("0\n");
    else
        printf("%d\n",MaxArraySum);
return 0;
}

这不应该在这个版吧！好多求最大子系列的，我不懂什么算法名字，凭感觉写了下，不知道能否经过极限测试！
#include <stdio.h>
void main()
{
    int i,j,k,s,n,l,h,a[100000];
    scanf("%d",&n);
    for(i=0;i<n;i++)scanf("%d",&a[i]);
    k=0;l=0;h=0;
    for(i=0;i<n;i++)
    {
        for(j=i,s=0;j<n;j++)
        {
            s=s+a[j];
            if(s>k)
            {
                k=s;
                l=i;
                h=j;
            }
        }
    }
    printf("序号%d到%d的最大和为%d。\n",l,h,k);
}
测试数据运行结果如下：
6
-2 11 -4 13 -5 -2
序号1到3的最大和为20。

我觉得直接给出代码不好。就在这个版写了。

我没有权限移帖子了！

用动态规划解决

[此贴子已经被作者于2015-10-24 08:29编辑过]

sum[n]表示以不大于n为起点，n为终点的最大子数和

sum[i] = max{sum[i-1]+a[i], a[i]}

动态规划以前看过，还不会列转移方程。。