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.
defmaximumSum(a,m):prefix_sum=0max_modulo_sum=0prefix_sums=[]fornumina:# Update the prefix sum modulo mprefix_sum=(prefix_sum+num)%m# Update max_modulo_sum with the current prefix_summax_modulo_sum=max(max_modulo_sum,prefix_sum)# Binary search to find the smallest prefix sum greater than the current prefix_sumlo,hi=0,len(prefix_sums)whilelo<hi:mid=(lo+hi)// 2ifprefix_sums[mid]>prefix_sum:hi=midelse:lo=mid+1iflo<len(prefix_sums):# There exists a prefix sum greater than the current onemax_modulo_sum=max(max_modulo_sum,prefix_sum-prefix_sums[lo]+m)# Insert the current prefix_sum into the sorted listprefix_sums.insert(lo,prefix_sum)returnmax_modulo_sum
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Maximum Subarray Sum
You are viewing a single comment's thread. Return to all comments →