fork(12) download 
  1. /*Morgan Stanley Test Question:
  2. Given a set of n coins of some denominations (may be repeating, in random order), and a number k.
  3. 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.
  4. In this manner give the highest sum of coins he/she can collect.*/
  5.  
  6. #include <stdio.h>
  7. #include <stdlib.h>
  8.  
  9. int sum(int* seq,int s,int e) //calc sum seq[s...e]
  10. {
  11. 	int i,res=0;
  12. 	for(i=s;i<=e;i++)res+=seq[i];
  13. 	return res;
  14. }
  15.  
  16. int main() //input, n, k, sequence and calc. sum with dp rules
  17. {
  18. int n,k,i;
  19. int seq[100];
  20. int dp[100][2];
  21. int seltd[100];
  22.  
  23. printf("How many nos. in the seq.? ");
  24. scanf("%d",&n);
  25.  
  26. printf("\nk? ");
  27. scanf("%d",&k);
  28.  
  29. printf("\nEnter the seq.:\n");
  30. for(i=0;i<n;i++)
  31. 	scanf("%d",&seq[i]);
  32.  
  33. dp[0][0]=0;
  34. dp[0][1]=seq[0];
  35.  
  36. for(i=1;i<k;i++) //initialize for upto k terms
  37. 	{
  38. 		dp[i][0]=dp[i-1][1];
  39. 		dp[i][1]=dp[i-1][1]+seq[i];
  40. 	}
  41.  
  42. int max,j;
  43. for(i=k;i<n;i++)
  44. 	{
  45. 		max=0;
  46. 		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
  47.  
  48. 		for(j=1;j<=k;j++) //for each i, select max sum, selecting a term to put out from seq[i-k...i-1]
  49. 			{
  50. 				if(dp[i-j][0]+sum(seq,i-j+1,i) > max)
  51. 				{
  52. 					max=dp[i-j][0]+sum(seq,i-j+1,i);
  53. 				}
  54. 			}
  55. 		dp[i][1]=max;
  56. 	}	
  57.  
  58. printf("\n\nArrays:\n");
  59. for(i=0;i<n;i++)
  60. 	printf("dp[%d] (%d,%d)\n",i,dp[i][0],dp[i][1]);
  61.  
  62. int flag=0;
  63. printf("\nSum: %d\n",dp[n-1][0]>dp[n-1][1]?dp[n-1][0]:(flag=1,dp[n-1][1]));	
  64.  
  65. return 0;
  66. }
  67.  
Success #stdin #stdout 0s 2296KB
comments (?)
stdin 
7
3
1 2 3 4 5 6 7
stdout 
How many nos. in the seq.? 
k? 
Enter the seq.:


Arrays:
dp[0] (0,1)
dp[1] (1,3)
dp[2] (3,6)
dp[3] (6,9)
dp[4] (9,13)
dp[5] (13,18)
dp[6] (18,24)

Sum: 24
https://ideone.com/1LvkJe
language:
C (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!