Friday, January 10, 2014

Largest Sum Subarray

You are given a binary array with N elements: d[0], d[1], ... d[N - 1].
d[i] can only be 0 or 1
You can perform AT MOST one move on the array: choose any two integers [L, R], and flip all the elements between (and including) the L-th and R-th bits. L and R represent the left-most and right-most index of the bits marking the boundaries of the segment which you have decided to flip.
What is the maximum number of '1'-bits (indicated by S) which you can obtain in the final bit-string?
import copy

def max_subarray(array):
    # Start & End indices of the max subarray 
    start = end = 0

    # Temporary Variable to hold the new Start
    t_start = 0

    # Holds the latest max sum
    # starts with array[0] because it addresses the 
    # case where all the elements in the array are
    # negative numbers.
    max_ending_here = max_so_far = array[0]

    # Holds the max subarray
    # Starts with the first element array[0]
    maxsubarray = t_maxsubarray = [array[0]]

    for index, x in enumerate(array[1:]):
        # max(x, max_ending_here + x) => max_ending_here
        if x > max_ending_here + x:
            # This is where the set starts
            t_start = index + 1
            t_maxsubarray = []
            max_ending_here = x
        else:
            max_ending_here = max_ending_here + x

        # max(max_so_far, max_ending_here) => max_so_far
        if max_so_far < max_ending_here:
            # The set ends here
            t_maxsubarray.append(x)
            # This is the latest max subarray
            maxsubarray = copy.deepcopy(t_maxsubarray)
            # Update the new Start index
            start = t_start
            # Update the new End index
            end = index + 1
            max_so_far = max_ending_here
        else:
            t_maxsubarray.append(x)

    print maxsubarray
    print start, end
    print max_so_far
Reference: [WIKI] Maximum Subarray Problem