this can be done in O(n) time and O(n) space: let count = the number of 1s seen so far - the number of 0s seen so far so for each element if it is 1 then count++ and if it is 0 count-- (count is 0 at first ) make a map m[] such that m[i] is null if count was never equal to i else it is the index of the first place where count was equal to i so at each step if m[count] is not null this means that the index we are on - m[count] is a subsequence such that number of 0s and 1s is equal the maximum over length of all such subsequences would be the result
here's a code for it note: count can be at least -n and at most n so the size of m must be 2n+1 so i shifted all by n and -1 here means null codepad.org/9zth8Uzl -- 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.
