Demo entry 3863580

Max Subarray

   

Submitted by anonymous on Mar 04, 2016 at 03:03
Language: Python. Code size: 661 Bytes.

# Finding the Maximum Subarray 
# Input: Array[n]

# max up to current index 
maxEndingHere = 0

# current maximum continuous segment
globalMax = 0

# indices 
(maxStartIndex, maxEndIndex) = 0

# sets start index to 1
currentStartIndex = 1

# loops for index from 1 to n 
for i in range(1, n): 

    maxEndingHere = maxEndingHere + array[currentEndIndex]

    if maxEndingHere > globalMax:
        return (globalMax, maxStartIndex, maxEndIndex) = (maxEndingHere, currentStartIndex, currentEndIndex)

    if maxEndingHere < 0:
        maxEndingHere = 0
        currentStartIndex += 1

    return (globalMax, maxStartIndex, maxEndIndex)

This snippet took 0.00 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).