# CFR 788 A. Functions again ( DP )

Problem - A - Codeforces

The first line contains single integer n (2 ≤ n ≤ 1e5) — the size of the array a.
The second line contains n integers a1, a2, ..., an (-1e9 ≤ ai ≤ 1e9) — the array elements.

dp[ i ][ j ] : 以下標 i 的元素結尾，下一次是加正的 ( j = 1 ) / 加負的( j = 2 )，此時的最大獲益。

O( N )

```#include <bits/stdc++.h>
using namespace std;

template< class T1, class T2 >
bool upmax( T1 &x, T2 v ){
if( x >= v ) return 0;
x = v; return 1;
}

const int MAXN = ( int ) 1e5;

int N;
int A[ MAXN ];

long long dp[ MAXN ][ 2 ];

signed main(){
ios::sync_with_stdio( 0 );
{
cin >> N;
for( int i = 0; i < N; ++i ){
cin >> A[ i ];
}
}
{
long long ans = - ( 1LL << 50 );
for( int i = 0; i <= MAXN; ++i ){
for( int j = 0; j < 2; ++j ){
dp[ i ][ j ] = - ( 1LL << 50 );
}
}
dp[ 0 ][ 0 ] = 0; // 0 -> next positive
for( int i = 1; i < N; ++i ){
upmax( dp[ i ][ 1 ], dp[ i - 1 ][ 0 ] + abs( A[ i ] - A[ i - 1 ] ) );
upmax( dp[ i ][ 0 ], dp[ i - 1 ][ 1 ] - abs( A[ i ] - A[ i - 1 ] ) );
upmax( ans, dp[ i ][ 1 ] );
upmax( ans, dp[ i ][ 0 ] );
upmax( dp[ i ][ 0 ], 0 );
}
cout << ans << endl;
}
return 0;
}
```