UC知道杭电ACM1003 WA~~~ 大虾帮下小弟
来源：百度知道 编辑：UC知道 时间：2024/06/22 20:24:22
#include<stdio.h>
int main()
{int i,T;
while(scanf("%d",&T)!=EOF)
{ for(i=1;i<=T;i++)
{int N,j,k,a[100000],x=0,y=0;
long int max,b[100000];
scanf("%d",&N);
for(j=0;j<N;j++)
scanf("%d",&a[j]);
b[0]=a[0];
for(j=1;j<N;j++)
b[j]=b[j-1]+a[j];
max=b[0];
for(j=1;j<N;j++)
if(b[j]>max)
{max=b[j];
y=j;
}
for(k=0;k<y;k++)
if((b[y]-b[k])>max)
{max=b[y]-b[k];
x=k+1;
}
printf("Case %d:\n%ld %d %d\n\n",i,max,x+1,y+1);
}
}
return 0;
}
int main()
{int i,T;
while(scanf("%d",&T)!=EOF)
{ for(i=1;i<=T;i++)
{int N,j,k,a[100000],x=0,y=0;
long int max,b[100000];
scanf("%d",&N);
for(j=0;j<N;j++)
scanf("%d",&a[j]);
b[0]=a[0];
for(j=1;j<N;j++)
b[j]=b[j-1]+a[j];
max=b[0];
for(j=1;j<N;j++)
if(b[j]>max)
{max=b[j];
y=j;
}
for(k=0;k<y;k++)
if((b[y]-b[k])>max)
{max=b[y]-b[k];
x=k+1;
}
printf("Case %d:\n%ld %d %d\n\n",i,max,x+1,y+1);
}
}
return 0;
}
动态规划
#include<iostream>
#include<fstream>
using namespace std;
int panduan(int a[],int b,int N)//返回一个负数向后多少位能加成正数
{
int temp=0,bb=b;
do{temp+=a[bb];bb++;}
while(temp<0&&bb<N);
if(temp>=0){return bb-b-1;}
else{return -1;}
}
int qiuzhi(int a[],int &shouwei,int &weishu,int N)
{
int t=0,sum=0;
while(a[t]<0&&t<N-1){t++;}shouwei=t+1;
if(a[t]<0)//说这一行的数组全是负数，直接找到一个最大值就行了
{
sum=a[t];
for(int i=0;i<N;i++)
{
if(a[i]>sum)
sum=a[i];
}
weishu=1;
}
else//如果不都是负数
{
int pp=t,oo;
do
{ t=0;
if(a[pp]>=0){sum+=a[pp];pp++;}
else
{
oo=panduan(a,pp,N);//从panduan函数返回的负数后面的位
if(oo!=-1)
{do{sum+=a[pp+t];t++;}//后面如果不是负的就加上
while(t<=oo);
pp=pp+t;}
else
break;//如果是负的，就这样的
}
}