刚刚还真是有点bug~就是第一个数是0时并且其它数都是负数时区间没有+1~
虽然改得不咋好看~不过还是改正了bug~

第一个数是输入要输入的数字~
后面才是正式输入数据内容~难怪会"出错"~

你可以到http://acm.hdu.里提交下，反正我按题意修改你的代码后提交不能AC。

这个问题还是先放放了~不能AC原因有很多~除了结果出错外还有输入格式不正确的可能~有些较好的AC平台会给出具体不能通过测试的案例~
我做这题就是练习一下算法并不打算去AC~感觉没啥问题就过了~如果真的找出出错具体原因再提出来~

看了下题目，求最大子序列和问题。
用暴力破解法，时间复杂度为O(n2)，超时。
基本思想是用分治策略，对于待求解数组A[m...n]，划分为A[m...mid]和A[mid + 1...n]，再对A[m...mid]和A[mid + 1...n]划分，直到区间足够小；
每一个区间都有3种可能的解：
1.S[i...j]完全位于A[m...mid]（S为待求的数组的解）；
2.S[i...j]完全位于A[mid + 1...n]；
3.S[i...j]位于A[m...mid]和A[mid + 1...n]之间；
对每个小区间求出以上的最大解，进而求出大区间的最大解，最后求出目标区间的最大解。
附上代码：

#include <stdio.h>
#include <stdlib.h>

struct result {
    int low;
    int high;
    int sum;
};

struct result find_max_mid_sum(int *, int, int, int);
struct result find_max_sum(int *, int, int);

int main() 
{
    int t, times = 0;
    scanf("%d", &t);
    while(times < t) {
        int k, n;
        int a[100000];
        scanf("%d", &n);
        for(k = 0; k < n; k++)
            scanf("%d", a + k);
        struct result res = find_max_sum(a, 0, k - 1);
        if(times)
            printf("\n");
        printf("Case %d:\n", times + 1);
        printf("%d %d %d\n", res.sum, res.low + 1, res.high + 1);
        times++;
    }
}

struct result find_max_mid_sum(int * a, int low, int mid, int high)
{
    int i;
    int sum = 0;
    int max_left = -1000;
    int max_left_idx = mid;
    for(i = mid; i >= low; i--) {
        sum += a[i];
        if(sum > max_left) {
            max_left = sum;
            max_left_idx = i;
        }
    }
    int max_right = -1000;
    int max_right_idx = mid;
    sum = 0;
    for(i = mid + 1; i <= high; i++) {
        sum += a[i];
        if(sum > max_right) {
            max_right = sum;
            max_right_idx = i;
        }
    }
    struct result res;
    res.low = max_left_idx;
    res.high = max_right_idx;
    res.sum = max_left + max_right;
    return res;
}

struct result find_max_sum(int * a, int low, int high)
{
    if(low == high) {
        struct result res;
        res.low = low;
        res.high = high;
        res.sum = a[low];
        return res;
    }
    else {
        int mid = (low + high) / 2;
        struct result left = find_max_sum(a, low, mid);
        struct result right = find_max_sum(a, mid + 1, high);
        struct result center = find_max_mid_sum(a, low, mid, high);
        if(left.sum > right.sum && left.sum > center.sum)
            return left;
        else if(right.sum > left.sum && right.sum > center.sum)
            return right;
        else
            return center;
    }
}

[此贴子已经被作者于2017-4-21 19:20编辑过]

#include<stdio.h>
int main()
{
    int*arr;int length;//数组长度
    int i;//遍历索引
    int sum;//局部区域之和
    int max;//最大子序列值
    printf("请输入数列元素个数：");
    scanf("%d",&length);
    arr=(int*)malloc(sizeof(int)*length);
    for(i=0;i<length;i++)
    {
        printf("请输入第%d个元素：",i+1);
        scanf("%d",&arr[i]);
    }
    max=arr[0];sum=0;
    for(i=0;i<length;i++)
    {
        sum+=arr[i];
        if(sum>max) max=sum;
        if(arr[i]>max)
        {
            max=sum=arr[i];
        }
    }
    printf("最大子序列之和：%d",max);
    return 0;
}

~/test # ./test 
请输入数列元素个数：13
请输入第1个元素：-6
请输入第2个元素：-7
请输入第3个元素：5
请输入第4个元素：4
请输入第5个元素：3
请输入第6个元素：-9
请输入第7个元素：-8
请输入第8个元素：5
请输入第9个元素：4
请输入第10个元素：3
请输入第11个元素：-1
请输入第12个元素：2
请输入第13个元素：1
最大子序列之和：12

有情况， 应该是14的

不能用sum和max直接比较~因为不能无视min取值的影响~
也不能直接用arr[i]和sum直接比较~因为arr[i]的取值是有累加性的~
例如

-10 3 -10 2 2

sum依次为
-10 -7 -17 -15 -13

这样个例子容易看出代码bug所在，2+2=4>3这样当然没有问题~但问题是这代码只利用了前面的一个2来做判断而把后面的2给忽略了~~~

6楼的代码应该没什么问题~正常情况下结果应该是不会出错的~至于为什么x版主说不能AC~大概就是对特殊值例如0和全部负数的空间取值细节没和题意匹配……~~~

[此贴子已经被作者于2017-4-21 23:45编辑过]

有错误哦
2
5 8 -5 1 -5 1
13 1 2


首先第一行输出2 可是只有一个Case就结束了
还有就是第二行输入5个数 输出了错误结果

#include <iostream>
#include <string.h>

int end, A;           //end,最大字串和的最后一个数字的下标加1, A,第几组测试
int arr[100];       //放置每行测试数据
int f[100];        //f[4]表示知道第四个数字的最大字串和
int main1(void)
{
    
    int N, n;                 //N总有几组测试数据, n每组有几个数字
    scanf_s("%d", &N);
    while (N--)                //可以循环输入
    {
        int start = 0;
        memset(arr, 0, 400);   //重置
        memset(f, 0, 400);      //重置
        scanf_s("%d", &n);     //每行n个数字
        
        int i = 0;
        while (n--)          //输入一组数字
        {
            scanf_s("%d", &arr[i++]);
        }

        int max = 0;        //当前最大的字串和的值
        int k = 0;         
        int j = 0;
        int t = i;
        int T=arr[0];     //
        int tt = 0;
        

        while (t--)          //找到第一个非负数就退出,或者(全部数字都是负数)找到最大的负数
        {
            if (arr[j++] >= 0)
            {
                t = 1;           //t=1，与下面隔10行的if(t==-1)对应
                break;
            }
            if (T<arr[t] && arr[t]<0)   //不断找较大的负数并记录下标
            {
                T = arr[t];
                tt = t;
            }
        
        }

        if (t == -1)           //全是负数
        {
            printf("Case %d:\n", A++);
            printf("%d %d %d\n\n", T,tt+1,tt+1);
            continue;
        }
        
        max = arr[j - 1];       //能到这里有,说明是有正数的
        start = j - 1;         //记下第一个正数的下标
        end = j - 1;           //
        f[j - 1] = arr[j - 1];
        
        //动态规划了
        for (int a = j; a < i; a++)      //i表示当前测试数字的总个数
        {
            if (arr[a] + f[a - 1] <= 0)      //3 -1 -4 -5, 此时f[0]=3, f[1]=2, f[2]=0, f[3]=0;  
            {
                f[a] = 0;
            }
            else if (f[a - 1] == 0 && arr[a] > 0)  //3 -1 -4 -5 10 此时 f[4]=10， 
            {
                k = a;                       //k只是暂时保存, 若f[a]>max, start=k
                f[a] = arr[a];
            }
            else
            {
                f[a] = f[a - 1] + arr[a];
            }

            if (f[a] > max)
            {
                max = f[a];
                start = k;
                end = a;

            }
            
        }
        
        printf("Case %d:\n", A++);
        printf("%d %d %d\n\n", max, start+1, end+1);
    }

    system("pause");

    return 0;
}

最大子序列和？那差不多就是这样了。

#include <stdio.h>
#include <stdlib.h>

int
main( void )
{
    int *array;
    int sum, t;
    int ix;
    int n;

    printf( "输入测试用例的数量：" );
    scanf( "%d", &n );
    array = ( int * )malloc( n * sizeof( int ) );
    printf( "输入测试用例的数值：\n" );
    for( ix = 0; ix < n; ++ix )
        scanf( "%d",&array[ ix ] );

    for( ix = 0, sum = 0, t = 0; ix < n; ++ix )
    {
        t += array[ ix ];
        if( t > sum )
            sum = t;
        else if( 0 > t )
            t = 0;
    }

    printf( "最大子序列和：%d", sum );

    return 0;
}

[此贴子已经被作者于2017-4-22 20:07编辑过]