수열의 연속한 구간에서 최댓값과 최솟값의 차를 모두 더한 것이 최대가 되도록 하는 것이 문제입니다.
구간들이 연속한 원소로 이루어져 있기 때문에 수열의 앞쪽으로 전진하면서 이미 계산한 답안을 통해 새로운 원소에 대한 값을 계산하는 DP 전략이 필요해 보입니다.
$n$번째 원소를 처리할 때, 탐색해볼 필요가 있는 경우는 많아야 $n$가지밖에 되지 않는다는 것을 알 수 있습니다.
$n$번째 원소를 포함하여 왼쪽으로 길이가 $1, 2, \cdots, n - 1, n$인 구간을 한 조로 구성하는 경우만이 새로 추가되기 때문입니다.
이 구간 왼쪽에서 남은 학생의 경우는 이전에 계산한 최적의 조대로 구성할 수 있으므로 다시 계산할 필요가 없습니다.
길이가 $1$인 구간을 계산하면서 최댓값과 최솟값을 같이 갱신할 수 있으므로 전체 계산 횟수는 $\sum_{n=1}^{N}n = O\left(N^2\right)$이 됩니다.
코드
fn solve(ability: &[u32]) -> u32 {
let mut point_until = vec![0; ability.len()];
for i in 1..ability.len() {
let mut max_point = 0;
let mut max_elem = ability[i];
let mut min_elem = ability[i];
for partition in (0..i).rev() {
let point = point_until[partition] + max_elem - min_elem;
max_point = std::cmp::max(max_point, point);
max_elem = std::cmp::max(max_elem, ability[partition]);
min_elem = std::cmp::min(min_elem, ability[partition]);
}
point_until[i] = std::cmp::max(max_elem - min_elem, max_point);
}
*point_until.last().unwrap()
}