求高手详细讲解http://acm.hdu.edu.cn/showproblem.php?pid=1003

Question

我的代码：#include<iostream>
using namespace std;
int f,l;
int Max(int a[],int n)
{
int i,j,t=-99999999,sum[100000];
sum[1]=a[1];
for(i=1;i<=n;i++)
{
for(j=i+1;j<=n;j++)
{
sum[j]=sum[j-1]+a[j];
if(t<sum[j])
{
t=sum[j];
f=i;
l=j;
}
}
}
return t;
}
int main()
{
int a[100000],t,n,m=1,i,M_sum;
cin>>t;
while(t--)
{
cin>>n;
for(i=1;i<=n;i++)
cin>>a[i];
M_sum=Max(a,n);
cout<<"case "<<m<<":"<<endl;
m++;
cout<<M_sum<<" "<<f<<" "<<l<<endl<<endl;
f=0;
l=0;
}
system("pause");
return 0;
}
我发现很多不良之处，但是不知道怎么改良。超时问题亟待解决！
听说用动态规划不会超时，麻烦各位大大帮帮忙，烦劳详细的用动态规划跟我讲解一下。。。。

Answer 1

根据题目特点，起点在负数后的第一个整数或a[0]，终点在某一负数前。思路如下：
先找出所有的负数，然后把整个数组进行分段，a[0]到第一个负数为第一段，以后每一段都是以负数开头正数结尾，对各段分别求和，这样问题就转换为少数的几段间的最大值和起始点问题.
例如：
7 0 6 -1 1 -6 7 -5
分为三段7 0 6 -1 为第一段n1，1 -6 为第二段n2，7 -5为第三段n3。
然后把n1,n2,n3用同样的方式分段，如此迭代，从而大大简化了数据量。最后用排列组合的方式求出最大的Sum，起始点为段的起始点。代码有时间另附。

追问

非常感谢。麻烦你把代码也发来吧。

追答

#include
#include
#include
int SqrSort(int *p,int c,int *n);

int main()
{
int n=1,m=0,i,j,s[20][3]={0},*p=NULL;
scanf("%d",&n);
for(j=0;jv)
m=i,v=n[0];
n[1]++;
if(n[0]>v)
n[2]=i;
else
n[0]=v,n[2]=m;
return 0;
}

Answer 2

#include<iostream>
using namespace std;
int f,l;
int Max(int a[],int n)
{
int maxelement = -1001, maxindex, tempmax, i, tempf, t;
tempmax = 0, tempf = 1;
t = -1001;
for(i=1;i<=n;i++)
{
if(maxelement < a[i])
{
maxelement = a[i];
maxindex = i;
}
if(tempmax+a[i]<0)
{
tempmax = 0;
tempf = i+1;
}
else
{
tempmax = tempmax+a[i];
}
if(tempmax > t)
{
t = tempmax;
f = tempf;
l = i;
}
}
if(maxelement <= 0)
{
t = maxelement;
f = l = maxindex;
}
return t;
}
int main()
{
int a[100000],t,n,m=1,i,M_sum;
cin>>t;
while(t--)
{
cin>>n;
for(i=1;i<=n;i++)
cin>>a[i];
M_sum=Max(a,n);
if(m>1) cout << endl;
cout<<"Case "<<m<<":"<<endl;
m++;
cout<<M_sum<<" "<<f<<" "<<l<<endl;
f=0;
l=0;
}
system("pause");
return 0;
}