The original statement…

“Given a set of n coins of some denominations (may be repeating, in random order), and a number k. A game is being played by a single player in following manner: Player can choose to pick 0 to k coins contiguously but will have to leave one next coin from picking. In this manner give the highest sum of coins he/she can collect.”

( from http://www.geeksforgeeks.org/morgan-stanley-interview-set-11-campus/ )

As per my understanding, the problem requires an algo to… optimally choose which integers to skip so that the ‘<=k-size partitioned blocks’ requirement holds and max. possible sum is obtained.

e.g. for k=3

{7 4 2 4 1 6 6} would be broken as “7…4” 2 “4” 1 “6…6”; sum=27

{1 2 3 4 5 6 7} as “1…2…3” 4 “5…6…7”; sum=24

With this understanding, I tried a DP solution on paper, which works for the 1st case…

- record total sum and keep indexes of first(f) elements of current ‘k-block’
- …and also the value(lval) and index(ldx) of lowest element

for i=0…n … - for the new (ith) element,
- if i-f<k, (i.e. block capacity not reached) - update sum and lowest element, if needed
- if i-f==k (i.e. block filled) - then rearrange as needed…

if a[i]<=lval, start a new block i.e. update f to i+1

else deduct lval from sum and rearrange current block assign f=ldx+1

This one works for 1st example but for second, it’d return only “5 6 7”, eliminating all the lower elements.

I’d be grateful for any answer or idea.

Thanks.