Max Sum

【求助】Max Sum
题目在 http://acm.hdu.edu.cn/showproblem.php?pid=1003

C/C++ code


#include<stdio.h>
#include<stdlib.h>
int a[100001];
int b[100001];        
int main(void)
{
    int t, n, m, i, j, max, start, end;
    scanf("%d", &t);
    for(m = 1; m <= t; m ++)
    {
        scanf("%d", &n);
        for(i = 1; i <= n; i ++)
        {
            scanf("%d", &a[i]);
            b[i] = a[i];
        }
        max = a[1];
        start = 1; 
        end = 1;
        for(i = 2; i <= n; i ++)
        {
            if(b[i - 1] > 0)
                b[i] += b[i - 1];
            if(b[i] > max)
            {
                max = b[i];
                end = i;
            }
        }
        for(j = end; j > 0; j --)   
            if(b[j] < 0)
            {
                start += j;
                break;
            }
        printf("Case %d:\n", m);
        printf("%d %d %d\n", max, start, end);
        if(m < t)
            printf("\n");
    }
    system("pause");
    return 0;
}

为什么在电脑上运行得好像没错啊，可是提交时却说答案错误？

谢谢各位，帮忙看看。

------解决方案--------------------
数组a有什么用啊？没有处理多解的情况吧？
------解决方案--------------------
最大子串问题，你可以google或者baidu。有多种算法，根据算法去实现，下面给你贴一种 Kadane算法。

C/C++ code

int Kadane(const int array[], size_t length, unsigned int& left, unsigned int& right)  
{  
    unsigned int i, cur_left, cur_right;  
    int cur_max, max;  
  
    cur_max = max = left = right = cur_left = cur_right = 0;  
  
    for(i = 0; i < length; ++i)  
    {  
        cur_max += array[i];  
  
        if(cur_max > 0)  
        {  
            cur_right = i;  
  
            if(max < cur_max)  
            {  
                max = cur_max;  
                left = cur_left;  
                right = cur_right;  
            }  
        }  
        else  
        {  
            cur_max = 0;  
            cur_left = cur_right = i + 1;  
        }  
    }  
  
    return max;  
}

相关推荐