一题acm题
http://dc.gdut.edu.cn:8000/JudgeOnline/showproblem?problem_id=1097


附上我没有通过的解题。

#include<stdio.h>
#include<stdlib.h>
int main()
{
long ma,m,max,M;
int i,j,N,flag;
int **ary;
scanf("%d",&N);
scanf("%ld",&M);
ary=(int **)malloc(sizeof(int *)*M);
for(i=0;i<M;++i)
{
ary[i]=(int *)malloc(sizeof(int)*N);
}

for(i=0;i<N;++i)
{
for(j=0;j<M;++j)
{
scanf("%d",(*(ary+i)+j));
}
}
scanf("%d%d",&i,&j);
m=0;ma=0;max=0;flag=0;
for(i=M-1;i>=0;--i)
{
ma = ary[0][i]+m;
if(ary[0][i]>0)flag=1;
for(j=0;j<N;++j)
{
if(ary[j][i]+m > ma)
ma = ary[j][i]+m;
if(ary[j][i]>0)flag=1;
}
if(flag==0)
{
m=0;
ma=0;
}
m=ma;
if(ma>max)max=ma;
}
if(max<0)printf("%d",0);
else
printf("%d",max);
return 0;

}

[解决办法]
你这样的算法就算结果正确也超时了，效率太低了
[解决办法]
思路是这样的，建立一个一维数组，长度等于二维数组的列数，把二维数组的每一列的最大的数保存在一位数组中（因为你要保证喜爱值的总和最大，所以肯定选择一列里最大的那个数），然后对一维数组里的连续的同号数进行相加（因为这些连续的同号数要么都选，要么都不选，所以相当于一个数），然后再从数组的反方向进行计算最大的喜爱值
[解决办法]
这道题绝不像你们想的那么简单，需要在算法上进行改进，
你们的算法时间复杂度是O（n*m），肯定超时了，试试这个怎么样（编译环境vc6.0）。

C/C++ code

#include <iostream>using namespace std;int merge(int a[], int len, int b[]){    int sum = 0;    int i = 0;    int len_b = 0;    while(i<len)    {        while(i<len && a[i]>=0)        {            sum += a[i];            ++i;        }        b[len_b++] = sum;        sum = 0;        if(i<len)        {            while(i<len && a[i]<=0)            {                sum += a[i];                ++i;            }            b[len_b++] = sum;            sum = 0;        }    }    return len_b;}void search(int a[], int len){    int val = a[0];    int val_temp = a[0];    for(int i=2; i<=len-1; i+=2)    {        if((val_temp+=a[i-1])>0)        {            val_temp = a[i];        }        else        {            val_temp = a[i];        }        if(val_temp>val)        {            val = val_temp;        }    }    cout<<val;}void foo(){    int row;    int column;    cin>>row>>column;    int *a = new int[column];    int i;    for(i=0; i<column; ++i)    {        cin>>a[i];    }    int temp;    for(int r=1; r<row; ++r)    {        for(int c=0; c<column; ++c)        {            cin>>temp;            if(temp>a[c])            {                a[c] = temp;            }        }    }        for(i=0; a[i]<=0 && i<column; ++i);    if(i==column)    {        int max = a[0];        for(int j=1; j<column; ++i)        {            if(max<a[i])            {                max = a[i];            }        }        cout<<max;        return;    }    int j;    for(j=column-1; a[j]<=0; --j);    int len = j-i+1;    int *b = new int[len];    len = merge(&a[i], len, b);    search(b, len);}int main(){    foo();    return 0;}