We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Search
  4. Maximum Subarray Sum
  5. Discussions

Maximum Subarray Sum

  • ArpitJai
     + 0 comments

    No need to use tree or sorted set. Just store all the prefix sums and sort. This idea comes from a different problem of minimising loss on house purchasing.

    def maximumSum(a, m):
    n = len(a)
    prefix_sums = [(a[0]%m,0)]
    for i in range(1,n):
        new_sum = a[i] + prefix_sums[i-1][0]
        prefix_sums.append((new_sum%m,i))
    prefix_sums.sort()
    max_sum = prefix_sums[-1][0]
    prev_index = prefix_sums[0][1]
    for i in range(1,n):
        if prefix_sums[i][0] == prefix_sums[i-1][0]:
            prev_index = max(prev_index, prefix_sums[i][1])
        else:
            if prefix_sums[i][1] < prev_index:
                max_sum = max(max_sum, prefix_sums[i-1][0] - prefix_sums[i][0] + m)
            prev_index = prefix_sums[i][1]
                
    return max_sum  

    q = int(input().