O(n) Divide and Conquer Python

  • 1

    This problem is better done using the normal single pass approach.
    But for those interested in Divide an Conquer, the logic is as follows:

    1. the divide step divides the array into left and right halves and recursively solves for both of them
    2. Each subproblem takes the following parameters as input
      maximum_sub_array_sum_rec(arr, st, end)
      (arr, st, end) => represents, the portion of the array corresponding to the subproblem.

    and returns the following tuple.
    left_sum, left_index, right_sum, right_index, max_sum
    left_sum = maximum sum of subarray starting from leftmost index.
    left_index = the index where the left_sum ends
    right_sum = maximum sum of subarray starting from rightmost index.
    right_index = the index where the right_sum ends
    max_sum = the result value, indicating the maximum sub array sum

    1. The merge step:
      the result for the combination of the 2 sub arrays, is the maximum of the following :
      a) solution for left sub array,
      b) solution for right sub array,
      c) sub array formed by combining the right_sum portion of left sub array + left_sum portion of the right sub array

    2. Once we have the solution, we need to recalculate the left_sum, left_index, right_sum, right_index portions for the merged array, for which we will reuse the left_sum, left_index and right_sum, right_index values that we obtained from both the left and right halves.

        def maxSubArray(self, arr):
            return self.maximum_sub_array_sum_rec(arr, 0, len(arr) - 1)[4]
        def maximum_sub_array_sum_rec(self, arr, st, end):
            if st == end: # base case, handle single element
                return arr[st], st, arr[st], end, arr[st]
            mid = st + (end - st)//2
            left_sum1, left_index1, right_sum1, right_index1, max_sum1 = self.maximum_sub_array_sum_rec(arr, st, mid)
            left_sum2, left_index2, right_sum2, right_index2, max_sum2 = self.maximum_sub_array_sum_rec(arr, mid + 1, end)
            # re-calculate left_sum, left_index for the merged array
            cur_max_sum_left, cur_left_index = self.recalculate_sum_index(arr, left_index1+1, end+1, 1, left_sum1, left_index1)
            # re-calculate right_sum, right_index for the merged array
            cur_max_sum_right, cur_right_index = self.recalculate_sum_index(arr, right_index2-1, st-1, -1, right_sum2, right_index2)
            res_sum = max(right_sum1 + left_sum2, max_sum1, max_sum2) # calculate the resultant max sub array sum of merged array
            return cur_max_sum_left, cur_left_index, cur_max_sum_right, cur_right_index, res_sum
        def recalculate_sum_index(self, arr, start, end, step, sum, index):
            sum_temp, cur_max_sum, cur_index = sum, sum, index
            for i in range(start, end, step):
                sum_temp += arr[i]
                cur_max_sum, cur_index = (sum_temp, i) if sum_temp > cur_max_sum else (cur_max_sum, cur_index)
            return cur_max_sum, cur_index

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.