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
Solution:
1. Worst case algorithm is to list all possible sub sequences and then find the one which is maximum.
2. Take another array which contains the sum of numbers of the orig array
new[i] = orig[0]+...orig[i];
Now we have to find out the sum of each subarray. If the sum of the subarray is half the number of element in the subarray, then check if this subarray can replace the previous maximum. If it can we will replace the current max with this subarray.
Each subarray sum can be found using the following formula
Sum of all elements from j till i = sum[i, j] = new[i] - new[j-1]
