Hard DP problem.

Revision en2, by DreamingBoy, 2016-12-13 13:17:18

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

like

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!

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru2 Russian DreamingBoy 2016-12-14 12:07:20 72 Мелкая правка: 'е спасибо!' -
en2 English DreamingBoy 2016-12-13 13:17:18 717 Tiny change: 'O(N ^ 2)\n~~~~~\n\' -
en1 English DreamingBoy 2016-12-13 12:56:26 857 Initial revision for English translation
ru1 Russian DreamingBoy 2016-12-13 09:55:33 856 Первая редакция (опубликовано)