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.
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.
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 →
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.