game_changer007's blog

problem maximization
By game_changer007, 11 years ago, In English

Hi,I tried to solve this problem during the contest but could not.Contest is over.Please Help

Basically it states that there are N numbers in an array A

initially sum=0

if i choose a number A[i] then i will add minimum of (A[i-1],A[i+1]) to my sum and will discard A[i] off the array,

Find such the maximum sum that can be obtained.Example

Input

5

1 1 4 2 5

Output

6

First of all, second element (1) will be removed. 1 will be added into the account, as min(1,4)=1. Remaining chips would be arranged as : 1 4 2 5.

Then fourth element (2) will be removed and 4 will be added into account. Remaining chips : 1 4 5.

Similarly proceed further. Final credits will be : 1+4+1 = 6.

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
11 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

This problem on HackerEarth was just copied from Artem and Array (which is why I quicksolved this one)..

→ Reply
»
11 years ago, hide # |
← Rev. 2  
Vote: I like it +1 Vote: I do not like it

I think that is simply dp problem. d[i ]=max (dp [i-1],dp[i -2]+a[i ]). Answer is dp [n].

→ Reply