maxSubArray.py

#Kadane's Algorithm
#Program to find maximum sub array in an array

class maxSubArray:
    def __init__(self, inpArr):
        self.inpArr = inpArr

    def findMaxSubArray(self):
        maxSum = 0
        currentSum = 0
        currentEnd = 0
        currentStart = 0
        maxEndIndex = 0
        maxStartIndex = 0
        while (currentEnd < len(self.inpArr)):
            currentSum += self.inpArr[currentEnd]
            if (currentSum > maxSum):
                maxSum = currentSum
                maxStartIndex = currentStart
                maxEndIndex = currentEnd
            if (currentSum < 0):
                currentSum = 0
                currentStart = currentEnd + 1
            currentEnd += 1
        print ("maxSum: {0} \nmaxStartIndex: {1} \nmaxEndIndex: {2}".format(maxSum, maxStartIndex, maxEndIndex))
        print self.inpArr[maxStartIndex:maxEndIndex+1]

if __name__:
    inpArr = [1, 2, 3, -90, 6, 7, -2, 10,-123, 12]
    #inpArr = [-2, 4, -2, 7, 4, -8, -6, 2, 9, 1, 0, -4]
    obj = maxSubArray(inpArr)
    obj.findMaxSubArray()