Inverting sub-array to get maximum 1’s.

Let there be an array containing only two different elements. Lets consider them to be 0 and 1. You have to find total number of 1’s you could make from this array after performing some task. And the task is to select a sub-array and invert each of its element(Convert each of the element from 0 to 1 or 1 to 0 for every element in sub-array).

This problem certainly have a simple approach. Check for all subsets and count number of resulting 1’s in the array. That would result in an O(N3) solution and the pseudocode would look something like this

for i = 0 to n
    for j = i to n
        for k = i to j
            invert(elements)
            count(number of 1s)
            revert(elements)

That is very high complexity and surely is not expected. But the solution for above problem can be condensed to O(n) complexity. Yeah! That’s great!! But how?

First count number of 1’s in given array and store them(C). Now make another array such that for all 0’s in given array, corresponding indexes in new array have value 1 and for all 1’s in given array, corresponding indexes have value of -1. Now find Maximum sub-array sum for this new array. It gives number of 1’s that would be added by the sub-array to actual array after being inverted/flipped. It also removes all previously counted 1’s in that part of sub-array. How? all 0’s are 1’s now which will be added to MaxSubarray sum and all 1’s are -1’s now which will be subtracted from that sum.

Adding C and M would result in number of maximum 1’s that could be formed as per the question.

C = 0
M = 0
for i = 0 to n
    if A[i] = 1
        C = C+1
for i = 0 to n
    if A[i] = 1
        B[i] = -1
    else if B[i] = 0
        B[i] = 1
M = MaxSubarraySum(B)
print C + M
Example :
Array     :  1 0 0  1 0  1  1 0 0 0  1 0 0  1  1  1  1 0 0  1
Inverting : -1 1 1 -1 1 -1 -1 1 1 1 -1 1 1 -1 -1 -1 -1 1 1 -1
Count of 1's = 10
Maximum Subarray sum = 4

Answer for given array = 10 + 4 = 14
Final Array : 1 0 0 1 0 1 1 1 1 1 0 1 1 1 1 1 1 0 0 1
Advertisements

Maximum Subarray Sum algorithm

This algorithm is used to find the maximum sum of a contiguous sub array in a given array of integers. If the set of integers include only positive integers, maximum sum would be sum of all the elements of array. But when the array include negative integers too, the problem comes of how to solve it efficiently.

A naive approach would be finding sum of elements of all sub arrays.

MaxSubarraySumNaive(a[])
    max = 0
    for i = 1 to n
        for j = i to n
            temp = 0
            for k = i to j
                temp = temp + a[i]
            if temp > max
                max = temp
    return max

That’s an O(n3) solution which is not at all appreciable. So let’s learn this algo which could solve this problem with an O(n) complexity.

MaxSubarraySum(a[])
    max_sum = 0
    temp = 0
    for i = 1 to n
        temp = max( 0 , temp+a[i] )
        max_sum = max( max_sum , temp )
    return max_sum

This short function solves the problem in real quick time. Working of the function with an example is shown below

For increasing i,
Array elements  : 1 -2 8 -1  6  3 -12  4 -16  5 10
temp values     : 1  0 8  7 13 16   4  8   0  5 15
max_sum values  : 1  1 8  8 13 16  16 16  16 16 16