Hello Jalaj, I am not sure whether I have understood your approach corectly, but do you want to say that you will always get a subsequence with number of terms equal to twice the min(count0, count1)?
Consider for ex: 011110 The longest subsequence is 01 or 10, both of length 2(and none of length 4). PS: I am assuming by maximum subsequence, you meant longest. Nikhil Jindal On Sun, Jul 4, 2010 at 3:21 PM, jalaj jaiswal <[email protected]>wrote: > You are given an array ' containing 0s and 1s. Find O(n) time and O(1) > space algorithm to find the maximum sub sequence which has equal number of > 1s and 0s. > > Examples > 1) 10101010 > The longest sub sequence that satisfies the problem is the input itself > > 2)1101000 > The longest sub sequence that satisfies the problem is 110100 > My approach:---- in 1 go count the number of zero's and 1's .. find which > is smaller > then in the next scan take two count1 and count0 and start fetching o's and > 1's upto you get them to the smaller count(calculated earlier) > better answers ?? > > -- > With Regards, > Jalaj Jaiswal > +919026283397 > B.TECH IT > IIIT ALLAHABAD > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]<algogeeks%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > Please access the attached hyperlink for an important electronic communications disclaimer: http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
