kubrick
BAN USERyeah atul, exactly..here's my code
int max_punches_possible(int * weights, int index, int size)
{
int no_of_punch=0;
if(index>=(size-1))
{
no_of_punch=weights[index];
return no_of_punch;
}
if(weights[index]==0)
{
no_of_punch=max_punches_possible(weights,index+1,size);
return no_of_punch;
}
if(weights[index]<weights[index+1])
{
no_of_punch+=weights[index];
weights[index]=0;
weights[index+1]-=weights[index];
no_of_punch+=max_punches_possible(weights,index+1,size);
return no_of_punch;
}
no_of_punch+=weights[index];
no_of_punch+=max_punches_possible(weights,index+2,size);
return no_of_punch;
}
@anonymous: shudn't the answer be 7 punches for your example? here's how you get it :- with 3 punches you destroy the first 2 bags. then with 3 more you destroy bags 3 and 4. with a last punch you destroy the 5th bag which is left. this is exactly what happens if you follow my algo. do i get the question wrong?
- kubrick April 15, 2012int longest_alternating_subsequence(int *arr, int size)
{
int decreasing=1, i=0, length=0;
while(i<size-1)
{
while(decreasing&&(i<size-1))
{
if(arr[i+1]>arr[i])
{
decreasing=0;
length++;
i++;
}
else
i++;
}
while(!decreasing&&(i<size-1))
{
if(arr[i+1]<arr[i])
{
decreasing=1;
length++;
i++;
}
else
i++;
}
}
return length+1;
}
isn't this pivot i supposed to be the first i for which corresponding weight is non zero?? because if you start punching any of the other bags you decrease the weight of its *two* neighbours. but if you start by punching the leftmost nonzero bag and proceed rightways successively eliminating the bags to the left, you should get the maximum punches as with every punch you decrease the weight of only *one* bag, namely the bag's right neighbour . correct me if i'm wrong.
- kubrick April 15, 2012
the thing is, it can take max n punches to destroy n bags. let me explain when when number of punches required will be less than n..
- kubrick April 15, 2012suppose there is a series of bags whose weights are like:-
1 2 2 2.... ( m 2's) 1.
it can be proved that max m+1 punches are required to destroy this series of punching bags rather than the normal value of m+2.
thus we'll have to count the number of such patterns and thereby modify the number of punches accordingly. i'm not sure but i think this ultimately boils down to the greedy approach. although time complexity will be better.