Discussion on Maximum Subarray Sum Challenge

7 years ago+ 7 comments

The explanation is very helpful. For those implementing it in Python ... there is no Java like treeset in Python. A naive workaround is to use the bisect module which seems fast enough to solve this challenge:

from bisect import insort, bisect_right
def maximumSum(a, m):
    # Create prefix tree
    prefix = [0] * len(a)
    curr = 0;
    for i in range(len(a)):
        curr = (a[i] % m + curr) % m
        prefix[i] = curr
    
    # Compute max modsum
    pq = [prefix[0]]
    maxmodsum = max(prefix)
    for i in range(1, len(a)):
        # Find cheapest prefix larger than prefix[i]
        left = bisect_right(pq, prefix[i])
        if left != len(pq):
            # Update maxmodsum if possible
            modsum = (prefix[i] - pq[left] + m) % m
            maxmodsum = max(maxmodsum, modsum)

        # add current prefix to heap
        insort(pq, prefix[i])

    return maxmodsum

Cookie support is required to access HackerRank