POJ 2181 Jumping Cows

http://poj.org/problem?id=2181
初め、DP ( O(P^2) ) しようとしたけどP( <=150000 )が大きすぎるのでTLEした。
わからなくて結局写経した。
O(P)すげー。おもいつけるようになりたい

↓TLE実装

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX_N = 150000;
int N;
int a[MAX_N];

int solve(){
	int dp[2][N+1];
	int t, ans = 0;
	//dp[t][p] := (max value when cows administrated potoin (p-1) at the time t)
	dp[1][0] = 0;
	dp[0][0] = 0;
	for(int i = 1; i < N; i++){
		dp[1][i] = a[i-1];
	}
	for(t = 2; t <= N; t++){
		for(int i = 1; i <= N; i++){
			int u = (t%2 == 0) ? -1 : 1 * a[i - 1];
			dp[t%2][i] = max(dp[t%2][i-1], dp[(t+1)%2][i-1] + u);
		}
		ans = max(ans, dp[t%2][N]);
	}
	return ans;
}
int main(){
	scanf("%d", &N);
	for(int i = 0; i < N; i++){
		scanf("%d", &a[i]);
	}
	printf("%d\n", solve());
	return 0;
}

↓AC実装

#include <cstdio>
#include <algorithm>
using namespace std;

int N;
int main(){
	int od = 0, ev = 0;
	scanf("%d", &N);
	for(int i = 0; i < N; i++){
		int p;
		scanf("%d", &p);
		od = max(od, ev + p);
		ev = max(ev, od - p);
	}
	printf("%d\n", max(od, ev));
}

simple is the best