#include<iostream>
#include<stdio.h>
using namespace std;
int main()
{
freopen("in.txt","r",stdin);
int n;
while(cin>>n)
{
int a[n];
int sum=0;
int maxsum=0;
for(int i=0;
i<n; i++)
{
cin>>a[i];
sum+=a[i];
if(sum>maxsum)maxsum=sum;
if(sum<0)sum=0;
}
cout<<maxsum<<endl;
}
}| Problem Statement for BadNeighbors | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
#include <iostream>
#include<stdio.h>
using namespace std;
#define LEN 100
int donations[LEN];
int sum[LEN];
int maxDonations(int n)
{
for(int i=0;i<n;i++){
sum[i]=donations[i];
}
int maxsum1=sum[0],maxsum2=sum[1];
//0...n-2
for(int i=0;i<n-1;i++){
for(int j=0;j<i-1;j++){
if(sum[j]+donations[i]>sum[i])
sum[i]=sum[j]+donations[i];
if(sum[i]>maxsum1)maxsum1=sum[i];
}
}
for(int i=0;i<n;i++){
sum[i]=donations[i];
}
//1...n-1
for(int i=1;i<n;i++){
for(int j=1;j<i-1;j++){
if(sum[j]+donations[i]>sum[i])
sum[i]=sum[j]+donations[i];
if(sum[i]>maxsum2)maxsum2=sum[i];
}
}
return maxsum1>maxsum2?maxsum1:maxsum2;
}
int main()
{
int n;
freopen("in.txt","r",stdin);
while(cin>>n)
{
for(int i=0; i<n; i++)
{
cin>>donations[i];
}
cout<<maxDonations(n)<<endl;
}
return 0;
}
【动态规划初级】 BadNeighbors,布布扣,bubuko.com
原文：http://www.cnblogs.com/zhaokongnuan/p/e379e4feb641bbe2cde3934eca882e5f.html