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.
I am writing to try to explain how this works and why it's a very clever solution.
let's not consider the if inside the for loop, so the for loop basically just iterate over the combination of elements e.g. a[0], a[0:1], a[0:2] ...
The concern for most people would be all the other combination of elements, and many choose to Brute Force to see those other combination. But this is what makes this answer a clever one.
The secrete is the if statement. The max() is self-evident. pr - a1[ind] + m is the trick. pr is just the remainder after modulo for a[i], so pr + m gives the same remainder but larger than m (the smallest number larger than m that gives remainder to be pr). ind is the index that separate all the previous remainders into two parts, the left part (those remainders less or equal than pr), the right part (those remainders larger than pr). Well, for those remainders that are less or euqal to pr, (pr + m - a1[ind])%m < a1[ind] e.g. if pr=3, a1=[0,1,2,3,4,5], then (pr + m - a1[ind])%m <= 3 so there is not need to consider those part. For the right part, those larger than pr, the reason that it only considers the element at ind, a1[ind] is becaues that (pr + m - a1[ind]) gives a remainder, but the one at ind = bisect.bisect(a1,pr) gives the largest one, e.g. if pr=3, so the ind=4, and (pr + m - a1[ind]) = (3+7 - a1[4]) --> 6, but if we put a1[5] into it the result would be --> 5. 6>5>... is the reason it only considers the element at ind = bisect.bisect(a1,pr). For what is bisect, check this out: https://www.geeksforgeeks.org/bisect-algorithm-functions-in-python/
By subtracting a1[ind] in the (pr + m - a1[ind]) has the same effect as excluding one particular element from the a[i:j] sequence. I think the reason this answer is clever is that, normally people would think about the different combinations of elements, but this answer only consider eliminating one element from a sequence, hence it doesn't think about the nested for loop for an O(n^2) answer. And this oberservation on the key role of the element at ind=bisect.bisect(a1,pr) combining pr-a1[ind]+m is def a killer.
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 →
I am writing to try to explain how this works and why it's a very clever solution.
let's not consider the
ifinside the for loop, so the for loop basically just iterate over the combination of elements e.g. a[0], a[0:1], a[0:2] ...The concern for most people would be all the other combination of elements, and many choose to Brute Force to see those other combination. But this is what makes this answer a clever one.
The secrete is the
ifstatement. The max() is self-evident.pr - a1[ind] + mis the trick.pris just the remainder after modulo for a[i], sopr + mgives the same remainder but larger than m (the smallest number larger than m that gives remainder to be pr). ind is the index that separate all the previous remainders into two parts, the left part (those remainders less or equal than pr), the right part (those remainders larger than pr). Well, for those remainders that are less or euqal to pr,(pr + m - a1[ind])%m < a1[ind]e.g. if pr=3, a1=[0,1,2,3,4,5], then(pr + m - a1[ind])%m <= 3so there is not need to consider those part. For the right part, those larger than pr, the reason that it only considers the element at ind, a1[ind] is becaues that(pr + m - a1[ind])gives a remainder, but the one at ind = bisect.bisect(a1,pr) gives the largest one, e.g. if pr=3, so the ind=4, and (pr + m - a1[ind]) = (3+7 - a1[4]) --> 6, but if we put a1[5] into it the result would be --> 5. 6>5>... is the reason it only considers the element at ind = bisect.bisect(a1,pr). For what is bisect, check this out: https://www.geeksforgeeks.org/bisect-algorithm-functions-in-python/By subtracting a1[ind] in the
(pr + m - a1[ind])has the same effect as excluding one particular element from the a[i:j] sequence. I think the reason this answer is clever is that, normally people would think about the different combinations of elements, but this answer only consider eliminating one element from a sequence, hence it doesn't think about the nested for loop for an O(n^2) answer. And this oberservation on the key role of the element at ind=bisect.bisect(a1,pr) combiningpr-a1[ind]+mis def a killer.