## krgaurav22

BAN USERIf the input is : 10, 12, 20

Your formula gives 21 which is wrong.

#include<iostream>

using namespace std;

char *str(char *s);

char *str(char *s)

{

int i=0,j=0,k=0;

char tmp1=s[k],temp2=s[++k];

while(s[i]<97)

i++;

while(s[i]!='\0')

{

s[j++]=tmp1;

tmp1=temp2;

temp2=s[++k];

s[j++]=s[i++];

}

s[j]='\0';

return s;

}

int main()

{

char *s;

cin>> s;

cout<<str(s);

return 0;

}

I think it can be done in O(kn) where k is subarray size and n is the given array size.

Let A be the array of numbers with size n.

Let C be an array such that C[i,j] contains the possible subsets of size j from array A with size i.

We want C[n,k]. We will find it by Dynamic Programming using Memoized version.

Here is the algorithm:

SET(A,n,k)

for i<-1 to n

f

C[i,1]={A[i]}

for j<-1 to n

for i<-1 to k

C[j,i]=empty set

return MEMOIZED(A,C,n,k)

MEMOIZED(A,C,n,k)

if k=0 or n=0

C[n,k]=empty set

else if k=1 and C[n,k]=empty set

for j<-1 to n

C[n,k]=C[n,k] U {A[j]}// here U adds subset {A[j]} to set of subsets in C[n,k]

return C[n,k]

if n<k

return C[n,k]

if n=k

C[n,k]= MEMOIZED(A,C,n-1,k-1) U A[n] //here U will add A[n] to every subset in C[n-1,k-1]

else

C[n,k]= MEMOIZED(A,C,n-1,k) U (MEMOIZED(A,C,n-1,k-1) U A[n])

return C[n,k]

Clearly we reach each box in array C only once .So Time Complexity is O(kn)

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window

Try this: 1,8,3,4,10 . It proves ur expression wrong.

- krgaurav22 January 08, 2016dp[i] = max(dp[i-1], v[i] + dp[i-2], v[i] + dp[i-3])