Maximum_Subarray_Problem [DivideAndConquer]

# -*- coding: utf-8 -*-

'''
Author: Shakib Haris
Problem: Maximum Subarray Problem
Solution: Divide and Conquer // O(n lg n)
Input: The Change(s) of Price, not the Prices
Output: Maximum Subarray
'''



def findMaxCrossingSubarray(A, lo, mid, hi):
    leftSum = float('-inf')
    Sum = 0
    for i in range(mid, lo - 1, -1):
        Sum += A[i]
        if Sum > leftSum:
            leftSum = Sum
            maxLeft = i
    rightSum = float('-inf')
    Sum = 0
    for i in range(mid + 1, hi + 1):
        Sum += A[i]
        if Sum > rightSum:
            rightSum = Sum
            maxRight = i

    return maxLeft, maxRight, leftSum + rightSum



def findMaxSubarray(A, lo, hi):
    if lo == hi:
        return lo, hi, A[lo]
    else:
        mid = (lo + hi) // 2
        leftLo, leftHi, leftSum = findMaxSubarray(A, lo, mid)
        rightLo, rightHi, rightSum = findMaxSubarray(A, mid + 1, hi)
        crossLo, crossHi, crossSum = findMaxCrossingSubarray(A, lo, mid, hi)

    if leftSum >= rightSum and leftSum >= crossSum:
        return leftLo, leftHi, leftSum
    elif rightSum >= leftSum and rightSum >= crossSum:
        return rightLo, rightHi, rightSum
    else:
        return crossLo, crossHi, crossSum



def display(A):
    for item in A:
        print("%d " %item, end = "")
    print("")



A = [int(x) for x in input().split()]
print("Original Array: ", end = "")
display(A)
start, end, maxSum = findMaxSubarray(A, 0, len(A) - 1)
print("Max Sum: %d\nSub-array: " %maxSum, end = "")
display(A[start:end + 1])