Maximum_Subarray_Problem [Kadane's Algorithm]

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

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

def kadane (A):
    maxEndingHere = A[0]
    maxSoFar = A[0]
    lenA = len(A)
    start = end = tStart = 0

    for i in range(1, lenA):
        maxEndingHere += A[i]

        if maxEndingHere < A[i]:
            maxEndingHere = A[i]
            tStart = i

        if maxSoFar < maxEndingHere:
            maxSoFar = maxEndingHere
            start = tStart
            end = i

    return start, end, maxSoFar


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 = kadane(A)
print("Max Sum: %d\nSub-array: " %maxSum, end = "")
display(A[start:end + 1])