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.
Please take a look at this explanation. IMHO is a better explained than the editorial.
Solved the question finally with the help of this great video https://youtu.be/u_ft5jCDZXk . Explained really well step by step till the last. Do watch if you are struggling hard. The question will seem quite easier after watching this.
Do upvote this if you find it helpful
C++ Solution.
long maxSum(vector<long> a, long m) { long sum = 0, max = LONG_MIN, result = LONG_MAX; set<long> s; for (int i = 0; i < a.size(); i++) { sum = (sum + a[i]) % m; a[i] = sum; max = std::max(max, sum); } for (auto x: a) { auto p = s.insert(x); if (++p.first != s.end()) { result = min(*p.first - x, result); } } return std::max(max, m - result); }
Java solution:
static long maximumSum(long[] a, long m) { long maxSum=0; TreeSet<Long> prefix = new TreeSet<Long>(); long currSum=0; for(int i=0;i<a.length;i++){ currSum=(currSum+a[i]%m)%m; maxSum=Math.max(maxSum, currSum); Long pr = prefix.higher(currSum); if(pr != null){ maxSum= Math.max(maxSum, (currSum-pr+m)%m); } prefix.add(currSum); } return maxSum; }
Sort 308 Discussions, By:
Please Login in order to post a comment