How to select a subset from an array so that the sum of the elements of the subset is maximum ?
But there is one interesting condition : -
1)When I select any particular element, I am forced to select the next and previous element as well.
What will be the recurrence-relation/dynamic-programming approach to solve this problem?
Example:- [-10,1,2,3,-5,-6,7,8,9]
We select ‘2’ and ‘8’ and our final answer is, hence :- [1+2+3] + [7+8+9] = 30
Say [1,2,3,4,5]…
If you select ‘2’ and ‘4’, answer will be= 1+2+3+4+5
I have formed a recurrence relation but not very sure about it…
@ssjgz @l_returns 
This problem has been created by me , btw…
Update :- I finally discovered a solution on my own .
4 Likes
What if edge elements are selected?
Also, if I select 2, which includes (1, 2, 3), I can’t select 3 or -5 again right? Because that’ll include 2 or 3 twice in the subset.
Yes, only for “1” time!
Say [1,2,3,4,5]…
If you select ‘2’ and ‘4’, answer will be= 1+2+3+4+5
Select a subset having minimum sum and also no two adjacent elements should have less than 3 elements in between.
This is simpler than previous one and seems like some classical DP.
dp[k] will depend dp[j] where j<k-3.
Try and let me know if you still can’t find it. I will share exact solution with you. But giving this much hint seems enough.
Btw why r u sharing it publicly ?
You could have shared it with Codechef or some other platform and many coders could have enjoyed solving it.
1 Like
Actually I created this problem while sleeping and got impatient for solution. I’ll delete the post. Thanks
1 Like
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 
1 Like
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
Why won’t it mean that way. Didn’t got your doubt.
Counter example ?
I still think my solution should work.
Ik but who says there can’t be a different solution if we modify this problem little bit ?
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.
Hey, @l_returns can you tell me your solution idea…you can DM me if you want
1 Like
Itna formal mat ho, fb par lunga teri fir 
1 Like
I already told my idea. Can you give me a counter case when you say it shouldn’t work ?
1 Like
So that was your complete idea??
1 Like
Sum - (minimum sum such that no two have less than three elements in between) is my idea.
1 Like
Are you sure it will always be max?
1 Like
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
Sum - min is always max I think. Nope ?
I am not 100% Sure but I think it should work.
Tell me one reason why it shouldn’t.
1 Like
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 
1 Like