Apple

Description

有一张很长的桌子，上面放了一排苹果，每个苹果有一个能量值， 正能量(正数)吃了会增加开心值，负能量（负数）吃了会减少开心值。

游戏规则：  两个人分别站在桌子的最左和最右。左右都能先开始游戏。 

每个人有三种选择

①吃自己面前的苹果并向对方移动 ②直接向对方移动。 ③不吃苹果你的游戏结束，等待对方。

每次选择都有限制条件： 如果上一次你选了①那么当前只能选①，③中的一个 如果上一次你选②那么当前只能选①，②，③中的一个 如果上一次你选③的话，你的游戏结束。两人游戏都结束或者两人相遇，全局游戏结束。

（移动的距离为一个苹果的位置，两人初始开心值为0）

Input

测试数据为多组，对于每组测试数据：

每组数据的的第一行输入一个n，然后下面输入n个苹果， a[i]代表第i个苹果的能量值。 ( 1<=n<=1e5,-1000<=a[i]<=1000)

Output

输出两人玩一次游戏，一起能得到的最大开心值，如果为负数，输出0；

Sample Input Copy

1 2 3 5 -1 1 2 3 -1

Sample Output Copy

6 6

 这个题的意思真的有点难理解，WA了两次才懂得真正的含义；

就是求最大字段和，并不是最大区间和，我们可以正着来一遍，在到这来一遍，然后再相加比较最大值即可：

#include<stdio.h> #include<stdlib.h> #include<iostream> #include<algorithm> #include<math.h> #include<string.h> #include<queue> using namespace std; int a[100010]; int dp1[100010]; int dp2[100010]; int main() { int n; while(~scanf("%d",&n)) { for(int i=1;i<=n;i++) scanf("%d",&a[i]); int num1=0,sum=0,num2=0; for(int i=1;i<=n;i++) { if(num1<0) num1=a[i]; else num1+=a[i]; sum=max(sum,num1); dp1[i]=sum; } sum=0; for(int i=n;i>0;i--) { if(num2<0) num2=a[i]; else num2+=a[i]; sum=max(sum,num2); dp2[i]=sum; } int maxx=0; for(int i=2;i<=n;i++) maxx=max(maxx,dp1[i-1]+dp2[i]); maxx=max(maxx,dp1[n]); printf("%d\n",maxx); } return 0; }