Conquer Maximum Sum Subarray with Divide & Conquer Algorithm
There are many ways of finding the maximum sum subarray of
n integers. One way of solving the problem of finding the maximum sum subarray is using the divide & conquer algorithm. To solve the problem, one needs to divide the array recursively into 2 parts, find the maximum subarray for the left part, the right part, and the part that crosses the midpoint for each of the divided parts, and calculate the answer for the current array from those.So, the pseudocode for the algorithm would be:
def max_subarray(a):
# Base cases
if len(a) == 0:
return float('-inf'), float('-inf'), float('-inf')
if len(a) == 1:
return a[0], a[0], a[0]
# Divide (get answers for left and right parts)
ll, lmax, lr = max_subarray(a[:len(a) // 2])
rl, rmax, rr = max_subarray(a[len(a) // 2:])
lsum = sum(a[:len(a) // 2])
rsum = sum(a[len(a) // 2:])
# Obtain 3 numbers and return max-prefix, max-suffix, and total maximum sum
return conquer(ll, lmax, lr, lsum, rl, rmax, rr, rsum)In this problem, you are asked to implement the
conquer part where given 8 numbers, you should correctly find 3 numbers that represent the best prefix-sum, the best sum that crosses the midpoint, and the best suffix-sum. The 8 given numbers are:- The best prefix sum for the left subarray
- The maximum sum of the left subarray
- The best suffix sum of the left subarray
- The sum of all the numbers in the left subarray
- The best prefix sum for the right subarray
- The maximum sum of the right subarray
- The best suffix sum of the right subarray
- The sum of all the numbers in the right subarray
Input
The only line of the input contains 8 integers in the order described above. All the integers don’t exceed in absolute value.
Output
The program should print 3 numbers - the best prefix sum, the best sum that crosses the midpoint, and the best suffix sum.
Examples
Input | Output |
7 13 9 6 7 9 3 -2 | 13 16 7 |
7 13 9 6 5 25 3 1 | 11 25 10 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB