Sort Array

Given an array of size n wherein elements keep on increasing monotically upto a certain location
after which they keep on decreasing monotically, then again keep on increasing, then decreasing
again and so on. Sort the array in place (ie. using only O(1) extra memory).

Solution:
Step1: Find the point after which the decrease starts let us call it P1. O(logn)
Step2: From P1 reverse the array. O(n)
Step3: Mark the beginning of the array as P2.
Step4: Now start a inplace merge sort, where first array begins at P1 and other at P2. O(n)

Maximum Sub Sequence of 1s and 0s

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]