# Max-Teilfeld-Problem
# Quelle: Cormen et al., S. 73, 74

from sys import maxsize as UNENDLICH

def FindMaxCrossingSubarray (links,mitte,rechts):
    linkeSumme = -UNENDLICH
    summe = 0

    # Schleife: for i = mitte downto links
    i = mitte
    while i >= links:
        summe = summe + A[i]
        if summe > linkeSumme:
            linkeSumme = summe
            maxLinks = i
        i = i-1

    rechteSumme = -UNENDLICH
    summe = 0

    # Schleife: for j = mitte + 1 to rechts
    j = mitte + 1
    while j <= rechts:
        summe = summe + A[j]
        if summe > rechteSumme:
            rechteSumme = summe
            maxRechts = j
        j = j+1

    return (maxLinks, maxRechts, linkeSumme + rechteSumme)

def FindMaximumSubarray (links,rechts):
    if rechts == links:
        return (links, rechts, A[links])
    else:
        mitte = (links+rechts) // 2
        (linksLinks,linksRechts,linkeSumme) = \
            FindMaximumSubarray (links,mitte)
        (rechtsLinks,rechtsRechts,rechteSumme) = \
            FindMaximumSubarray (mitte+1,rechts)
        (mittigLinks,mittigRechts,mittigeSumme) = \
            FindMaxCrossingSubarray (links,mitte,rechts)
        if (linkeSumme >= rechteSumme) and (linkeSumme >= mittigeSumme):
            return (linksLinks,linksRechts,linkeSumme)
        elif (rechteSumme >= linkeSumme) and (rechteSumme >= mittigeSumme):
            return (rechtsLinks,rechtsRechts,rechteSumme)
        else:
            return (mittigLinks,mittigRechts,mittigeSumme)


A = ["", 13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]

l,r,summe = FindMaximumSubarray (1,16)

print ("Array: A =", A)
print ("MaxTeilfeld: A[%d..%d], Summe: %d" % (l,r,summe))