Ibrahim-Elsayed's blog

By Ibrahim-Elsayed, history, 16 months ago, In English

How to solve this problem using DP?

Tags help, dp
  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
16 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Calculate $$$dp_i$$$ as max value possible on prefix $$$i$$$. So at $$$i$$$-th position $$$dp_i = \max(dp_{i-2} - a_i - a_{i-1}, dp_{i-1} + a_i)$$$