Привет CodeForces.

Я не буду давать ссылку на задачу и даже объяснять условия задачи, потому-что эту задачу можно решить более легким способом. Но я хочу реализовать свою идею, но есть сложности в реализации и прошу вас помочь разобраться с этими сложностями.

В задаче требуется пересчитывать динамику

for (int i = 1; i <= n; i++){
  int mn = inf, mx = -inf;
  for (int j = i; j >= 1; j--){
    mn = min(mn, a[j]), mx = max(mx, a[j]);
    dp[i] = max(dp[i], dp[j - 1] + (mx - mn));
  }
}

Но большие ограничения не позволяют сделать это за O(N ^ 2).

Думаю есть способ быстро считать dp[i] = max(dp[j - 1] + (mx[j] - mn[j])) для 1 <= j < i

mx[j] -> максимум от j до i

mn[j] -> минимум от j до i

Заранее большое спасибо!