Find max sum of two non-intersecting sub arrays

user_14731030 0
Viewed 379

Given an array of integers, take any two non-intersecting subarrays, A1 and A2. A subarray could be empty too. we have to return the max(sum(A1,A2)). The return value is the maximum possible sum of two subarrays of the given array.

My Thoughts:
Find the max sum subarray. This will give two new subarrays, the left of it and the right of it. Find the max sum subarray left and right and choose the optimal one. I am not sure if this will yield the max answer.

Any ideas or approach?

algorithm
2 Answers

Find the max subarray ending at index i going left and find the max subarray ending at index i going right. Then for each candidate, update the best result with the larger of the current best or max_subarray_sum_on_the_left[i] + max_subarray_sum_on_the_right[i+1].

In case it was unclear -- when performing Kadane's algorithm for each direction, save for each index the best seen from that direction. This leads to an O(n) overall solution.

user_20347870
  1. Create array left[] such that left[i] = max subarray sum ending at index i (takes O(N) time)
  2. Create array right[] such that right[i] = max subarray sum starting at index i (takes O(N) time)
  3. Iterate over the arrays and keep track of the max value visited such that left[i] = max possible sum over all subarrays ending at i and right[i] = max possible sum over all subarrays starting at i. (takes O(N) time)
  4. Loop i from 1 to N-1, where i is the index about which we'll "partition" our array and choose non-intersecting subarrays. For a given i, the answer will be left[i] + right[i]

The solution has O(N) space and time complexity.

user_93507200
Related