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

5

Actually I created this problem while sleeping and got impatient for solution. I’ll delete the post. Thanks :slight_smile:

1 Like
6

Even if I select a subset with minimum sum and no 3 elements in between, it does not mean that sum-minimum sum= maximum sum . Didn’t get your idea :sweat_smile:

1 Like
7

There is a simpler version of this problem, which goes like this

1)If you select any element from the array, then you have to select the previous element as well.

For that, the dp relation is as follows :-

dp[i]= max(a[i]+a[i-1]+dp[i-2],dp[i-1])

1 Like
8

Why won’t it mean that way. Didn’t got your doubt.
Counter example ?
I still think my solution should work.

9

Ik but who says there can’t be a different solution if we modify this problem little bit ?

10

Why would you delete it now. Let it be. It’s already public now. You won’t be able to use it on Codechef contest at least.

11

Hey, @l_returns can you tell me your solution idea…you can DM me if you want :slight_smile:

1 Like
12

Itna formal mat ho, fb par lunga teri fir :stuck_out_tongue:

1 Like
13

I already told my idea. Can you give me a counter case when you say it shouldn’t work ?

1 Like
14

So that was your complete idea??

1 Like
15

Sum - (minimum sum such that no two have less than three elements in between) is my idea.

1 Like
16

Are you sure it will always be max? :stuck_out_tongue:

1 Like
17

You will have to take care of both borders. Otherwise I think this should work. If you have any counter case then please let me know.

1 Like
18

Sum - min is always max I think. Nope ?

19

I am not 100% Sure but I think it should work.
Tell me one reason why it shouldn’t. :sweat_smile:

1 Like
20

Try this testcase :–> [-10,1,2,3,-5,-6,7,8,9]

Min. Sum= -10-6=-16

Real answer =Total Sum- (-16 )

= 9+16
=25.

Answer should be 30 :frowning:

1 Like
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