LINEGAME - VOI09 Trò chơi với băng số
Tác giả: skyvn97
Ngôn ngữ: C++
#include<cstdio>
#include<iostream>
#define MAX 1000100
#define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1)
#define REP(i,n) for (int i=0;i<(n);i=i+1)
using namespace std;
typedef long long ll;
int a[MAX];
int n;
ll f[MAX][2];
template<class T>
void maximize(T &x,const T &y) {
if (x<y) x=y;
}
void init(void) {
scanf("%d",&n);
FOR(i,1,n) scanf("%d",&a[i]);
}
void optimize(void) {
f[1][1]=a[1];
f[1][0]=0LL;
FOR(i,1,n-1) REP(j,2) {
maximize(f[i+1][j],f[i][j]);
maximize(f[i+1][1-j],f[i][j]+(j<1)*a[i+1]-(j>0)*a[i+1]);
}
cout << max(f[n][0],f[n][1]);
}
int main(void) {
init();
optimize();
return 0;
}