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 agree. This was very tricky and there might be no way of solving this unless you know that special property of subarray sums.
But to try to explain it a little bit clearly, I think it's important to understand these points:
1) Subtracting the current modulo with the modulos before it will remove the effect of those modulos
- Since we are doing this to each element, then we are able to get the modulos on each subarrays.
Example: arr = [7,7,1,3] m = 9
* prefix = [7,5,6,0] (Modulos from 0 to i)
*
* We have 6 on index 2 and before it we have 7 on index 0
*
* ((6-7)+9)%9 = 8 (the highest possible modulo)
*
* When we subtract 7, we are removing its effect on our current modulo 6
*
* So, we are only considering subarray [7,1] that has mod 8
2) "You can maximize a modulo by subtracting it with the closest higher modulo than it."
* The result will always be negative since you are subtracting it with a number higher than it.
* You then add the resulting negative number to m and this will result to another possible positive modulo.
*
* The closer the number is to the modulo, the smaller the difference and the higher the resulting modulo will be (that's why we are looking for the closest higher modulo)
It's faster to use TreeSet in Java as it has the method higher which will return the closest higher element to your element in the tree.
That's because you take a difference. Say m=7, then you could have e.g. prefix values 2 and 5 (both are already % m). The difference is -3. You add 7 to get 4, which is the actual modulo you need.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Join us
Create a HackerRank account
Be part of a 26 million-strong community of developers
Please signup or login in order to view this challenge
Maximum Subarray Sum
You are viewing a single comment's thread. Return to all comments →
I agree. This was very tricky and there might be no way of solving this unless you know that special property of subarray sums.
But to try to explain it a little bit clearly, I think it's important to understand these points:
1) Subtracting the current modulo with the modulos before it will remove the effect of those modulos - Since we are doing this to each element, then we are able to get the modulos on each subarrays.
Example: arr = [7,7,1,3] m = 9 * prefix = [7,5,6,0] (Modulos from 0 to i) *
* We have 6 on index 2 and before it we have 7 on index 0 *
* ((6-7)+9)%9 = 8 (the highest possible modulo) *
* When we subtract 7, we are removing its effect on our current modulo 6 *
* So, we are only considering subarray [7,1] that has mod 8
2) "You can maximize a modulo by subtracting it with the closest higher modulo than it." * The result will always be negative since you are subtracting it with a number higher than it. * You then add the resulting negative number to m and this will result to another possible positive modulo. *
* The closer the number is to the modulo, the smaller the difference and the higher the resulting modulo will be (that's why we are looking for the closest higher modulo)
It's faster to use TreeSet in Java as it has the method higher which will return the closest higher element to your element in the tree.
@dianadoctor1995 can you help me understand why we are adding m to difference result here?
That's because you take a difference. Say m=7, then you could have e.g. prefix values 2 and 5 (both are already % m). The difference is -3. You add 7 to get 4, which is the actual modulo you need.