Maximum sum in an integer sequence with a partitioning constraint

general
, ,
1

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.

1 Like
2

You can just do some simple dp like :

dp[i][2] - what is the answer for the prefix [1…i],
0 - if not
1 - if the last contiguous block includes i

The complexity is O(n*k).

Because dp[i][1] = max(dp[i-1][0] + sum(i,i), dp[i-2][0] + sum(i-1,i), … , dp[i-k][0] + sum(i-k+1,i))
UPD1: It can be reduced to O(n), because we can keep some monotonic queue.

1 Like
3

I found this O(nlogn + nk) time and O(n) space algorithm… Let me know if it is wrong.

First we form pair that holds position and the array element. Then we sort it in descending order of array element.
We also create slots[] that tell us whether that element is chosen or not.
Then we iterate through that sorted array.

  1. We fill the slot to check to see if it forms k contiguous elements. (max O(2k) )

  2. If it cannot form, then we add it in sum.( variable to store the ans).

Answer will be sum.

4

1)How large can n,k be ?

1 Like
5

There’s no such constraint on n or k. (Obviosuly, if k>=n, then no coin’ll have to be skipped).
I’ve quoted exactly from the link (Morgan Stanley Interview | Set 11 (On-Campus) - GeeksforGeeks). So, no more details available. Though, I think sufficient detail is there.

6

For reference, here’s the implementation (with O(nk))…