Algorithms and Data Structures

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:
  1. The best prefix sum for the left subarray
  1. The maximum sum of the left subarray
  1. The best suffix sum of the left subarray
  1. The sum of all the numbers in the left subarray
  1. The best prefix sum for the right subarray
  1. The maximum sum of the right subarray
  1. The best suffix sum of the right subarray
  1. 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

To check your solution you need to sign in