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;  } 

 

查看更多 下一篇