Good point. Thanks.

So now I modify my answer to

No two adjacent element can have one or two element in between. ( It can have 0 elements, or 3,4,5… Elements in between)

Now do you have any counter case ?

dp[i] depends on dp[j] where j<k-3 or j=k-1 (in short j!=k-2 and j!=k-3)

Works ?

Now,

Say… [-5 4 199 -678 3 4 -1 -2 -3 566]

Now, min.sum= -678-2-3= -703

Answer= -5+4+199+3+4+(-1)+566(which is not allowed as you cannot select 566 without selecting -2 and -3 as well )

As I already said you’ll have to handle both borders.

So, now I’ll have to find a test case which will give WA even after handling corners. FML.

Hahaha.

One way of handling it can be

Append -infinity,0 to starting of array

And append 0,- infinity to ending of array

I am not very sure but this is my first idea to handle borders.

I never knew such easy looking problem will give me this much trouble.

Actually, there is a problem from past contests which asks you to do the same thing on a rooted tree.

I know that if I get to know how to solve it in array form, tree will be just so easy

Wow link ?

I would like to solve that problem.

Practicing DP for ACM icpc from today

Thanks for sharing array version.

**1)When I select any particular element, I am forced to select the next and previous element as well.**

If consider this for every selected element then you have to select all the elements in the array.

As to your example, you also have to select (-1,0,1,2,3,…) ‘0’ and simultaneously ‘-1’ as well. I think you should look into this. Correct me if I am wrong.

You don’t recurse the rule.

If you select element at ith index then you will mark i-1th and i+1th element as well. Dont recursively apply this rule to i+1th and i-1th element.

Let’s ask this to dp king @taran_1407.

Can you please tell me whether my solution should work or not ?

If not then any counter case ?

Can you tell me who is the dp_queen ??

Officially tarini ( because Taran is King)

But let’s not spam your own post by discussing this here.

I have solved this problem , I cannot define how happy I feel…

Used very simple logic lol.

I realized that knowing and studying too much can also be dangerous…sometimes you don’t open yourself up to new-ideas