CFR 788 A. Functions again ( DP )

Problem - A - Codeforces

題意：
給一個長度為 N 的數列 A[]。求最大的 f( l, r )，滿足 1 ≤ l < r ≤ n：

資料規模：
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 )，此時的最大獲益。
每次到達一個新的下標 i 就加入以 i 為左界的狀態，並以 i 為右界的狀態更新答案。

時間 / 空間複雜度：
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;
}