Hi CodeForces.

I won't give link of problen and explain statement of problem, because this problem has more easier solution. But i want implement my solution idea, but i have problems with realization, and i need your help.

In problem i must calculate dp

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));
  }
}

Problem can not be solved in O(N^2), because N <= 10^6

I think, exist way to calculate dp mush faster -> dp[i] = max(dp[j - 1] + (mx[j] - mn[j])) 1 <= j < i

mx[j] -> maximum from j to i

mn[j] -> minimum from j to i

Thanks in advance!