有兩種解法，首先看我的錯誤解法#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;
}
這種解法是我自己想的，大概思路就是把連續(xù)的正數(shù)加起來當做一個數(shù)。比如 1 2 -1 -2這四個數(shù)就相當于3和-1 -2。這樣就簡化了一點，然后按照這個新的數(shù)組遍歷，每次求出以某一個數(shù)開始的數(shù)列的最大值，如果第一個數(shù)是負數(shù)，那么就可以跳過，因為第一個是負數(shù)，加上他肯定會小。這種方法還要考慮到全部都是負數(shù)的情況。但是這樣時間還是太大，比如間斷的，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;
}
這種解法的關鍵就是沒輸入一個數(shù)字就加進去，每次最大的值保存下來，如果加入一個數(shù)為0后就從0開始，因為如果累加到和為負數(shù)的時候，說明前面的最大和已經(jīng)求出來了，所以就從0開始。給大佬跪下。
解法二:動態(tài)規(guī)劃
dp[i]表示以a[i]為結尾的最大和。所以每次只要比較dp[i-1]+a[i]和dp[i]的最大值就可以。還是不知道動態(tài)規(guī)劃怎么想，就是dp[i]表示什么想不通.
