# O(n) Divide and Conquer Python

• 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
``````

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