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)
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])