Maximum Subarray Sum

  • + 1 comment

    This can be made a little more efficient. You're using bisect_left, followed by insort later, which is a combination of bisect followed by insert. So you're basically repeating the bisect step when you could just use the index gotten from the first bisect step. You can also avoid a little bit of confusion by using bisect, instead of bisect_left and remove the +1. The following passes all test cases.

    import bisect
    
    def maximumSum(a, m):
        mm,pr=0,0
        a1=[]
        for i in a:
            pr=(pr+i)%m
            mm=max(mm,pr)
            ind=bisect.bisect(a1,pr)
            if(ind<len(a1)):
                mm=max(mm,pr-a1[ind]+m)
            a1.insert(ind, pr)
        return mm