How to select a subset from an array so that the sum of the elements of the subset is maximum?

21

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 ?

1 Like
22

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 :blush:)

1 Like
23

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

24

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

Hahaha.

1 Like
25

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.

1 Like
26

Sorry @anon55659401 :frowning:
:joy:

1 Like
27

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 :stuck_out_tongue:

1 Like
28

Wow link ? :stuck_out_tongue:
I would like to solve that problem.
Practicing DP for ACM icpc from today :grin:
Thanks for sharing array version.

1 Like
29

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.

30

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.

1 Like
31

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 ?

1 Like
32

Can you tell me who is the dp_queen ?? :stuck_out_tongue:

33

Officially tarini :stuck_out_tongue: ( because Taran is King)
But let’s not spam your own post by discussing this here. :stuck_out_tongue:

1 Like
34

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

Used very simple logic lol. :stuck_out_tongue:

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

2 Likes