CODEWITHSUNDEEP
pythonalgorithm
Steve P.
Steve P.

Reputation: 14709

Issue getting the beginning of a max subarray

I am trying to implement a method to get the maxSubArray sum and the associated beginning and end indices. For reference, the maxSubArray is the contiguous subArray whose integer sum is the largest amongst all subArrays. I have the sum correct, and the end index correct, but I am having trouble with getting the beginning. I have accounted for one trivial case, but no matter what I do, I can't seem to account for all of the cases. Whenever I account for one, another emerges. Obviously getting the sum is possible in linear time, but I can't seem to figure out a way to get the correct start index efficiently. 

def maxSubArray(seq):
    #max_i = max ending at i, max_gen = best max up until i
    max_i = max_gen = beg = end = prev_max = 0

    for i in xrange(len(seq)):
        #use dynamic programming to get maxSubArray sum (works)
        max_i = max(0, max_i + seq[i])
        max_gen = max(max_gen, max_i)

        #get correct end (works)
        if prev_max < max_gen:
            end = i

        prev_max = max_gen

    if max_gen == 0:
        max_gen = max(seq)
        beg = end = seq.index(max_gen)

    return [max_gen, beg, end]

Like I said, I tried many things, but keep on deleting them as every new way introduces new/old problems. Anyone have any advice/a solution? I saw a similar question under the Java tag, but the answers were not correct. For convenience, I have included a brute force method, which I know works, and the mini-tester that I've been using:

def bruteForceCheck(seq):
    maxV = [float('-inf'), 0, 0]

    for i in xrange(len(seq)):
        for j in xrange(i,len(seq)):
            if (sum(seq[i:j+1]) > maxV[0]):
                maxV = [sum(seq[i:j+1]), i, j]

    return maxV

if __name__ == "__main__":

    for i in xrange(1000):
        l = []
        for j in xrange(15):
            num = random.randint(-1000,1000)

            #didn't feel like dealing with issue of two methods 
            #choosing to count or not count 0s
            while (num == 0):
                num = random.randint(-1000,1000)

            l.append(num)

        msa = maxSubArray(l)
        bfc = bruteForceCheck(l)

        if msa != bfc:
            print l
            print msa
            print bfc
            break

Upvotes: 3

Views: 214

Answers (2)

Paul Draper
Paul Draper

Reputation: 83393

Forgive me, but this works and is Pythonic.

def maxSubArray(seq):
    all_sum = cur_sum = 0
    all_beg = cur_beg = 0
    all_end = 0
    for cur_end, x in enumerate(seq, 1):
        if cur_sum + x > 0:
            cur_sum += x
            if all_sum < cur_sum:
                all_sum = cur_sum
                all_beg, all_end = cur_beg, cur_end
        else:
            cur_sum = 0
            cur_beg = cur_end
    return all_sum, all_beg, all_end

The algorithm is the same. There is the sum, beginning index, and end index, for an array ending here (cur_) and overall (all_).

EDIT: Note that the end index here is exclusive.

Also, if there are multiple optimal subarrays, this returns the first and longest.

Upvotes: 2

wwii
wwii

Reputation: 23783

This problem seemed familiar to me ... a quick search turned up a wikipedia article Maximum subarray problem. Adapated from the c++ solution in that article

def maxSubArray(seq):
    max_so_far = seq[0]
    max_ending_here = 0
    begin = 0
    begin_temp = 0
    end = 0
    for i in xrange(1, len(seq)):
        if max_ending_here < 0:
            max_ending_here = seq[i]
            begin_temp = i
        else:
            max_ending_here += seq[i]
        if max_ending_here >= max_so_far:
            max_so_far = max_ending_here
            begin = begin_temp
            end = i
    return max_so_far, begin, end

Upvotes: 1

Related Questions