
Sponsored
Sponsored
Use these hints if you're stuck. Try solving on your own first.
What's the score after reversing a sub-array [L, R] ?
It's the score without reversing it + abs(a[R] - a[L-1]) + abs(a[L] - a[R+1]) - abs(a[L] - a[L-1]) - abs(a[R] - a[R+1])
How to maximize that formula given that abs(x - y) = max(x - y, y - x) ?
This can be written as max(max(a[R] - a[L - 1], a[L - 1] - a[R]) + max(a[R + 1] - a[L], a[L] - a[R + 1]) - value(L) - value(R + 1)) over all L < R where value(i) = abs(a[i] - a[i-1])
This can be divided into 4 cases.