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.
IMHO this one is so difficult because the trick to beating the time limits is to know or recognize a mathematical property of an array of modulo prefix sums.
Once you know that property you can use trees or a sorted array to search for the answer without testing every single permutation of sum[i][j].
I feel like this property is not related to coding and should have been stated up front. Perhaps that was intentional and part of the challenge, but it's easy to waste a lot of time coding before realizing you have to solve a math riddle first.
Can you elaboaret for about "array of modulo prefix sums" and share your code if possible.
Still I am not getting how cna I implment this. I've implement my solution with DP but I am getting timeout error but I've checked individul or for small set of tesr case it's working fine and getting correct answer.
This link, which is also posted further down in the discussion, explains it: StackOverflow Explanation
Given a sum array where Si = the modulus sum of A0 to Ai, a subarray within A0-Ai will only produce a larger mod sum if Sj (j = start of the subarray) is greater than Si and as close to Si as possible.
Knowing this you can build a binary tree, or binary search a sorted array, to discover if a sub array results in a larger mod sum than the mod sum at Si. You don't have to calulate the mod sum of every possible subarray.
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.
Maximum Subarray Sum
You are viewing a single comment's thread. Return to all comments →
IMHO this one is so difficult because the trick to beating the time limits is to know or recognize a mathematical property of an array of modulo prefix sums.
Once you know that property you can use trees or a sorted array to search for the answer without testing every single permutation of sum[i][j].
I feel like this property is not related to coding and should have been stated up front. Perhaps that was intentional and part of the challenge, but it's easy to waste a lot of time coding before realizing you have to solve a math riddle first.
Hi Daniel,
Can you elaboaret for about "array of modulo prefix sums" and share your code if possible.
Still I am not getting how cna I implment this. I've implement my solution with DP but I am getting timeout error but I've checked individul or for small set of tesr case it's working fine and getting correct answer.
This link, which is also posted further down in the discussion, explains it: StackOverflow Explanation
Given a sum array where Si = the modulus sum of A0 to Ai, a subarray within A0-Ai will only produce a larger mod sum if Sj (j = start of the subarray) is greater than Si and as close to Si as possible.
Knowing this you can build a binary tree, or binary search a sorted array, to discover if a sub array results in a larger mod sum than the mod sum at Si. You don't have to calulate the mod sum of every possible subarray.
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.
I am running a little short on time and spent considerable amount of time with this question,really frustrating when this happens. :/