UC知道最大和问题
来源：百度知道 编辑：UC知道 时间：2024/06/22 02:40:01
我在杭电ACM,做了这道题.但老是超时,请高手来帮忙
#include<iostream>
using namespace std;
void main()
{
int T,n,b,sum=0,max,a[100000],j,k,p,q;
cin>>T;
for(int i=0;i<T;i++)
{
cin>>n;
max=sum;
for(int i=0;i<n;i++)
{
cin>>b;
a[i]=b;
}
for(k=0;k<n;k++)
{
sum=0;
for(j=k;j<n;j++)
{
if(max<(sum+=a[j]))
{
max=sum;
p=k;
q=j;
}
}
}
cout<<max<<" "<<p<<" "<<q<<endl<<endl;
}
}
#include<iostream>
using namespace std;
void main()
{
int T,n,b,sum=0,max,a[100000],j,k,p,q;
cin>>T;
for(int i=0;i<T;i++)
{
cin>>n;
max=sum;
for(int i=0;i<n;i++)
{
cin>>b;
a[i]=b;
}
for(k=0;k<n;k++)
{
sum=0;
for(j=k;j<n;j++)
{
if(max<(sum+=a[j]))
{
max=sum;
p=k;
q=j;
}
}
}
cout<<max<<" "<<p<<" "<<q<<endl<<endl;
}
}
//O(n)的算法
#include<iostream>
using namespace std;
void main()
{
int T,n;
cin>>T;
int tmp = 0, max = 0;
int st = 0;
int p = -1, q = T+1;
int first;
for(int i=0;i<T;i++)
{
cin>>n;
if(i==0) first = n;
tmp += n;
if(tmp > max)
{
max = tmp;
p = st;
q = i;
}
if(tmp < 0)
{
tmp = 0;
st = i+1;
}
}
if(q<T) cout<<max<<" "<<p<<" "<<q<<endl<<endl;
else cout<<first<<" 0 0"<<endl;
}
牛！我也要做ACM题……