DCP49 - Subarray with max sum

'''
This problem was asked by Amazon.
Given an array of numbers, find the maximum sum of any contiguous subarray of the array.
For example, given the array [34, -50, 42, 14, -5, 86], the maximum sum would be 137, since we would take elements 42, 14, -5, and 86.
Given the array [-5, -1, -8, -9], the maximum sum would be 0, since we would not take any elements.
Do this in O(N) time.
'''

# Function 1
def solve(array):
    # ******************************************************************************
    # ALL THE ITEMS RETURNED WILL BE TUPLES WITH 2 ELEMENTS
    # 1ST WILL BE THE MAX SUM AND SECOND THE LIST FROM WHICH THIS MAX SUM COMES FROM
    # ******************************************************************************
    n = len(array)
    if n == 1:
        if array[0] < 0:
            print("The array " + str(array) + " has only one element, that is also negative (" + str(array[0]) + "), so answer = 0 (must be positive or zero)")
            return 0, [0]
        else:
            return array[0], [array[0]]
    # Here, we go for n >= 2
    maxSum = 0
    maxList = list()
    for elementsTaken in range(n-1, 0, -1):
        # Example ----> I take 5 elements (2 possible lists if my array is length = 6)
        for firstIndex in range(0, n + 1 - elementsTaken):
            SUMLIST = list()
            # i = first index between the consecutive elements
            for i in range(elementsTaken):
                SUMLIST.append(array[firstIndex+i])
            if sum(SUMLIST) > maxSum:
                maxSum = sum(SUMLIST)
                maxList = SUMLIST.copy()

    return maxSum, maxList


# FUNCTION 2
def prettyPrint(array):
    SUM, SUMLIST = solve(array)
    # I want to check the special case of having only one negative element in my array (SUM = 0)
    print(str(array) + " ----> The sublist " + str(SUMLIST) + " has the elements with max sum = " + str(SUM))

# MAIN FUNCTION
array0 = [0]
array1 = [20]
array2 = [-10]
array3 = [10, 40]
array4 = [100, 25]
array5 = [34, -50, 42, 14, -5, 86]
array6 = [10, -3, 28, 9, -10, 8, -20, 18]
array7 = [-5, -1, -8, -9]
arrays = [array0, array1, array2, array3, array4, array5, array6, array7]
for i in range(len(arrays)):
    print("******** " + str(i+1) + " ********")
    prettyPrint(arrays[i])
    print()