The Maximum Subarray

  • + 0 comments

    Python

    def getmaxsubsequence(arr):
        total = 0
        for elem in arr:
            if elem > 0:
                total += elem
        return total if total > 0 else max(arr)    
    
    def getmaxsubarray(arr):
        maxbeforeindex = [arr[0]]
        for index in range(1, len(arr)):
            curvalue = arr[index]
            connectedvalue = curvalue + maxbeforeindex[index-1]
            maxbeforeindex.append(max(connectedvalue, curvalue))
        
        return max(maxbeforeindex)
    
    def maxSubarray(arr):
        return [getmaxsubarray(arr), getmaxsubsequence(arr)]