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_farReference: [WIKI] Maximum Subarray Problem

## No comments :

## Post a Comment