Codeforces Round #276 (Div. 1) Problem D - Kindergarten

Follow Up to this post.

Problem Statement:
484D - Kindergarten

Solution:
This is a rare problem where you have an \(O(N)\) DP solution :P
Firstly notice that if we have a group of students[i..j] such that students[i..m] are in increasing order and students[m..j] are in decreasing order, it is always better (or at least equal) to break them up int students[i..m] and students[m..j] (strictly speaking student[m] must only belong to either one of them, but you get the idea).

As such, we describe the students as having maximum and minimum peaks, such that in between two adjacent peaks, students are either in increasing or in decreasing order only. As such the sociability of a group is just the difference between the two ends of the group segment. In this manner, we can do a very simple DP:
Let M(i) be the maximum sociability possible by grouping students in [i..N]. Let the next peak that is closest to i in [i..N] is p. Then:
M(i) = max{ |charisma[i] - charisma[p-1]| + M(p), |charisma[i] - charisma[p]| + M(p+1) }
The information about the next closest peak from all i must be memoized before hand to arrive with an \(O(N)\) solution.

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

int a[1000003];
int peaks[1000003];
long long dp[1000003];
int N;

long long labs(long long a, long long b){
    long long ret = a-b;
    if(ret < 0) ret = -ret;
    return ret;
}

void solve(){
    int p = N-1;
    int state = 0;
    for(int i=N-2;i>=0;--i){
        if (state == 0){
            if(a[i] < a[i+1]){
                state = 1;
            }
            else if(a[i] > a[i+1]){
                state = -1;
            }
        }
        else if(state == 1){
            if(a[i] > a[i+1]){
                state = -1;
                p = i+1;
            }
        }
        else if(state == -1){
            if(a[i] < a[i+1]){
                state = 1;
                p = i+1;
            }
        }
        peaks[i] = p;
        
    }
    dp[N-1] = 0;
    for(int i=N-2;i>=0;--i){
        dp[i] = max(labs(a[i], a[peaks[i]]) + dp[peaks[i]+1],
                    labs(a[i], a[peaks[i]-1]) + dp[peaks[i]]);
    }
    cout << dp[0] << endl;
}

int main(){
    scanf("%d", &N);
    for(int i=0;i<N;++i){
        scanf("%d", &a[i]);
    }
    solve();
    return 0;
}