求AC代码及详细解释（也就是推导思路）
Wujitu的RP守恒时间限制：1500 ms | 内存限制：8192 KB
描述
话说天下的RP是守恒的，你的RP高了，我的RP可能就低了，你今天RP高了，明天RP可能就低了。我们的RP总是在高高低低中不断变化。有些事情做了是可以涨RP的，有的事情做了是要降RP的。
Wujitu在发现了这个道理后，决定在期末考试前多多积累人品。他发现，他做的每件事情对RP有如下影响：
（1） 他做了的第一件事情是涨RP的
（2） 如果他做的上一件事情是涨RP的，那么他做的下一件事情是降RP的
（3） 如果他做的上一件事情是降RP的，那么他做的下一件事情是涨RP的
Wujitu现在积攒的人品是0。涨RP记为RP值增加，降RP记为RP值减少。
Wujitu在期末考试前有N件事情可以做，每件事情都有自己的RP系数。对于这些事情，Wujitu只可以有两种选择：做，不做。事情的先后顺序是一定的，也就是说Wujitu只可以按照给定好的顺序选择做不做该事情。
现在请你帮助Wujitu在期末考试之前，积攒到最多的RP。
输入
每组数据包括两行，第一行有一个整数N（N<=1000000），代表有N件事情；第二行有N个正整数，代表每件事情的RP值Ri[正数]
Ri<=1000000
输出
输出结果仅包含一个整数,即Wujitu在期末前能积攒的最大RP值
样例输入
1
1
4
1 3 1 2
样例输出
1
4
希望能给出AC代码以及详细解释，这道DP题好像有后效应，不知道怎么做，望大牛赐教
在下面提交，谢谢！
http://www.
