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.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Search
  4. Maximum Subarray Sum
  5. Discussions

Maximum Subarray Sum

Problem
Submissions
Leaderboard
Discussions
Editorial
Topics

Sort 308 Discussions, By:

votes

Please Login in order to post a comment

  • danieltaylor
    5 years ago+ 3 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.

    50|
    Permalink
  • bitman09
    7 years ago+ 8 comments

    Please take a look at this explanation. IMHO is a better explained than the editorial.

    50|
    Permalink
    View more Comments..
  • visheshaggarwal1
    2 years ago+ 1 comment

    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

    27|
    Permalink
  • craig53
    3 years ago+ 6 comments

    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);
    }
    
    19|
    Permalink
    View more Comments..
  • palazares
    3 years ago+ 1 comment

    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;
        }
    
    14|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature