有两种解法，首先看我的错误解法#include<stdio.h>
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
int a[1000000];
int i,j,num=0,sum=0,temp=0,f=0,idex=0;
for(i=0;i<n;i++)
scanf("%d",&a[i]);
for(i=0;i<n;i++)
{
if(a[i]<=0)
f++;
}
if(f==n)
{
sum=-100000;
for(i=0;i<n;i++)
{
if(sum<a[i])
sum=a[i];
}
printf("%d",sum);
continue;
}
for(i=0;i<n;i++)
{
if(a[i]>0)
idex++;
if(idex>0)
{
if(a[i]<0)
{
if(temp>0)
{
a[num]=temp;
num++;
}
a[num]=a[i];
num++;
temp=0;
continue;
}
temp+=a[i];
if(i==n-1)
a[num++]=temp;
}
}
for(i=0;i<num;i++)
{
temp=0;
if(a[i]<0)
{
continue;
}
for(j=i;j<num;j++)
{
temp+=a[j];
if(sum<temp)
sum=temp;
}
}
printf("%d",sum);
}
return 0;
}
这种解法是我自己想的，大概思路就是把连续的正数加起来当做一个数。比如 1 2 -1 -2这四个数就相当于3和-1 -2。这样就简化了一点，然后按照这个新的数组遍历，每次求出以某一个数开始的数列的最大值，如果第一个数是负数，那么就可以跳过，因为第一个是负数，加上他肯定会小。这种方法还要考虑到全部都是负数的情况。但是这样时间还是太大，比如间断的，1 -2 3 -4 5 -6.。。这样的，那么时间肯定会蹦，所以我这种菜鸡写的就被out了，来看大佬的解法。
解法一
#include<stdio.h>
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
int i,x,sum=0,max=-20000;
for(i=0;i<n;i++)
{
scanf("%d",&x);
sum+=x;
if(max<sum)
max=sum;
if(sum<0)
sum=0;
}
printf("%d",max);
}
return 0;
}
这种解法的关键就是没输入一个数字就加进去，每次最大的值保存下来，如果加入一个数为0后就从0开始，因为如果累加到和为负数的时候，说明前面的最大和已经求出来了，所以就从0开始。给大佬跪下。
解法二:动态规划
dp[i]表示以a[i]为结尾的最大和。所以每次只要比较dp[i-1]+a[i]和dp[i]的最大值就可以。还是不知道动态规划怎么想，就是dp[i]表示什么想不通.
网友评论