/*Morgan Stanley Test Question:
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.*/
#include <stdio.h>
#include <stdlib.h>
int sum( int * seq, int s, int e) //calc sum seq[s...e]
{
int i, res= 0 ;
for ( i= s; i<= e; i++ ) res+= seq[ i] ;
return res;
}
int main( ) //input, n, k, sequence and calc. sum with dp rules
{
int n, k, i;
int seq[ 100 ] ;
int dp[ 100 ] [ 2 ] ;
int seltd[ 100 ] ;
printf ( "How many nos. in the seq.? " ) ;
printf ( "\n Enter the seq.:\n " ) ; for ( i= 0 ; i< n; i++ )
dp[ 0 ] [ 0 ] = 0 ;
dp[ 0 ] [ 1 ] = seq[ 0 ] ;
for ( i= 1 ; i< k; i++ ) //initialize for upto k terms
{
dp[ i] [ 0 ] = dp[ i- 1 ] [ 1 ] ;
dp[ i] [ 1 ] = dp[ i- 1 ] [ 1 ] + seq[ i] ;
}
int max, j;
for ( i= k; i< n; i++ )
{
max= 0 ;
dp[ i] [ 0 ] = dp[ i- 1 ] [ 1 ] > dp[ i- 1 ] [ 0 ] ? dp[ i- 1 ] [ 1 ] : dp[ i- 1 ] [ 0 ] ; //earlier bug - had dp[i-1][1] only - rectified wrt k=1 e.g. 5 1 2 6
for ( j= 1 ; j<= k; j++ ) //for each i, select max sum, selecting a term to put out from seq[i-k...i-1]
{
if ( dp[ i- j] [ 0 ] + sum( seq, i- j+ 1 , i) > max)
{
max= dp[ i- j] [ 0 ] + sum( seq, i- j+ 1 , i) ;
}
}
dp[ i] [ 1 ] = max;
}
for ( i= 0 ; i< n; i++ )
printf ( "dp[%d] (%d,%d)\n " , i
, dp
[ i
] [ 0 ] , dp
[ i
] [ 1 ] ) ;
int flag= 0 ;
printf ( "\n Sum: %d\n " , dp
[ n
- 1 ] [ 0 ] > dp
[ n
- 1 ] [ 1 ] ? dp
[ n
- 1 ] [ 0 ] : ( flag
= 1 , dp
[ n
- 1 ] [ 1 ] ) ) ;
return 0 ;
}
LypNb3JnYW4gU3RhbmxleSBUZXN0IFF1ZXN0aW9uOgpHaXZlbiBhIHNldCBvZiBuIGNvaW5zIG9mIHNvbWUgZGVub21pbmF0aW9ucyAobWF5IGJlIHJlcGVhdGluZywgaW4gcmFuZG9tIG9yZGVyKSwgYW5kIGEgbnVtYmVyIGsuCkEgZ2FtZSBpcyBiZWluZyBwbGF5ZWQgYnkgYSBzaW5nbGUgcGxheWVyIGluIGZvbGxvd2luZyBtYW5uZXI6IFBsYXllciBjYW4gY2hvb3NlIHRvIHBpY2sgMCB0byBrIGNvaW5zIGNvbnRpZ3VvdXNseSBidXQgd2lsbCBoYXZlIHRvIGxlYXZlIG9uZSBuZXh0IGNvaW4gZnJvbSBwaWNraW5nLgpJbiB0aGlzIG1hbm5lciBnaXZlIHRoZSBoaWdoZXN0IHN1bSBvZiBjb2lucyBoZS9zaGUgY2FuIGNvbGxlY3QuKi8KCiNpbmNsdWRlIDxzdGRpby5oPgojaW5jbHVkZSA8c3RkbGliLmg+CgppbnQgc3VtKGludCogc2VxLGludCBzLGludCBlKSAvL2NhbGMgc3VtIHNlcVtzLi4uZV0KewoJaW50IGkscmVzPTA7Cglmb3IoaT1zO2k8PWU7aSsrKXJlcys9c2VxW2ldOwoJcmV0dXJuIHJlczsKfQoKaW50IG1haW4oKSAvL2lucHV0LCBuLCBrLCBzZXF1ZW5jZSBhbmQgY2FsYy4gc3VtIHdpdGggZHAgcnVsZXMKewppbnQgbixrLGk7CmludCBzZXFbMTAwXTsKaW50IGRwWzEwMF1bMl07CmludCBzZWx0ZFsxMDBdOwoKcHJpbnRmKCJIb3cgbWFueSBub3MuIGluIHRoZSBzZXEuPyAiKTsKc2NhbmYoIiVkIiwmbik7CgpwcmludGYoIlxuaz8gIik7CnNjYW5mKCIlZCIsJmspOwoKcHJpbnRmKCJcbkVudGVyIHRoZSBzZXEuOlxuIik7CmZvcihpPTA7aTxuO2krKykKCXNjYW5mKCIlZCIsJnNlcVtpXSk7CgpkcFswXVswXT0wOwpkcFswXVsxXT1zZXFbMF07Cgpmb3IoaT0xO2k8aztpKyspIC8vaW5pdGlhbGl6ZSBmb3IgdXB0byBrIHRlcm1zCgl7CgkJZHBbaV1bMF09ZHBbaS0xXVsxXTsKCQlkcFtpXVsxXT1kcFtpLTFdWzFdK3NlcVtpXTsKCX0KCQppbnQgbWF4LGo7CmZvcihpPWs7aTxuO2krKykKCXsKCQltYXg9MDsKCQlkcFtpXVswXT1kcFtpLTFdWzFdPmRwW2ktMV1bMF0/ZHBbaS0xXVsxXTpkcFtpLTFdWzBdOyAvL2VhcmxpZXIgYnVnIC0gaGFkIGRwW2ktMV1bMV0gb25seSAtIHJlY3RpZmllZCB3cnQgaz0xIGUuZy4gNSAxIDIgNgoJCQoJCWZvcihqPTE7ajw9aztqKyspIC8vZm9yIGVhY2ggaSwgc2VsZWN0IG1heCBzdW0sIHNlbGVjdGluZyBhIHRlcm0gdG8gcHV0IG91dCBmcm9tIHNlcVtpLWsuLi5pLTFdCgkJCXsKCQkJCWlmKGRwW2ktal1bMF0rc3VtKHNlcSxpLWorMSxpKSA+IG1heCkKCQkJCXsKCQkJCQltYXg9ZHBbaS1qXVswXStzdW0oc2VxLGktaisxLGkpOwoJCQkJfQoJCQl9CgkJZHBbaV1bMV09bWF4OwoJfQkKCQpwcmludGYoIlxuXG5BcnJheXM6XG4iKTsKZm9yKGk9MDtpPG47aSsrKQoJcHJpbnRmKCJkcFslZF0gKCVkLCVkKVxuIixpLGRwW2ldWzBdLGRwW2ldWzFdKTsKCmludCBmbGFnPTA7CnByaW50ZigiXG5TdW06ICVkXG4iLGRwW24tMV1bMF0+ZHBbbi0xXVsxXT9kcFtuLTFdWzBdOihmbGFnPTEsZHBbbi0xXVsxXSkpOwkKCQpyZXR1cm4gMDsKfQo=