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
  • Practice
  • Certification
  • Compete
  • Career Fair
  • Hiring developers?
  1. Max Array Sum
  2. Discussions

Max Array Sum

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 392 Discussions, By:

votes

Please Login in order to post a comment

  • JoshZastrow
    3 years ago+ 0 comments

    To address with DP, work through the array, keeping track of the max at each position until you get to the last value of the array. You should start with the base cases defined before iterating through the remainder of the array.

    max @ position 0: value @ 0

    max @ position 1: either:

    • value @ 0
    • value @ 1

    from that point forward, the max of the next position is either:

    1. the current value at that position
    2. the max value found so far
    3. the max value from 2 positions back plus the current value

    keep track of the max at each position until you get to the last position of the array

    320|
    Permalink
  • williamlemens
    3 years ago+ 0 comments

    Java solution:

      public static int maxSubsetSum(int[] arr) {
        if (arr.length == 0) return 0;
        arr[0] = Math.max(0, arr[0]);
        if (arr.length == 1) return arr[0];
        arr[1] = Math.max(arr[0], arr[1]);
        for (int i = 2; i < arr.length; i++)
          arr[i] = Math.max(arr[i-1], arr[i]+arr[i-2]);
        return arr[arr.length-1];
      }
    

    This assumes that the empty set is a valid subset for this problem. It also assumes we're not going to need the input array for anything else, as it butchers that.

    Edit: checks for length of 0 & 1 (not checked by problem). Thanks @umanggupta

    66|
    Permalink
  • traviscoop
    3 years ago+ 0 comments

    I think this problem could use a better definition of what a subset is. Can a single element be a subset? The examples seem to say that it can't, because all of the enumerations of subsets never show a single element. However, the inputs for the problem say that the array could be as small as a single element. So, what would be the answer in that case? Or consider a case where a single element is larger than all other possible elements combined: 100, -1, -1 In this case, if I count a single element as a subset the answer would be 100, but if it isn't, then the answer would be 99.

    So, either a subset needs to include a single element. Or the constraints needs to change to say that 3 is the smallest length array possible.

    35|
    Permalink
  • nevvermind
    2 years ago+ 0 comments

    Geez, people. I appreciate you trying to explain things, but let's be honest: you won't be able to explain it better than 1000 blog posts or youtube videos found on the internets. If the algorithm has a name, please use it. That's what helps more.

    This HR problem is a small variation of something called Maximum subarray problem, of which its optimal algorithm is called Kadane's Algorithm. It's relatively simple. Everything is simple after you get it, I know - but this one is quite simple.

    Kadane's algo deals with sub-arrays made of every element, but, if you look at other solutions, you'll see that it only needs a small change to work for the current HR problem.

    Here's some links that helped:

    • https://en.wikipedia.org/wiki/Maximum_subarray_problem
    • https://www.youtube.com/watch?v=86CQq3pKSUw (I watched it 4 times. By the second watch, I was getting it.)

    Be patient, pay attention and don't give up.

    34|
    Permalink
  • xupremus
    3 years ago+ 0 comments
    int incl = 0, excl = 0, temp;
    for(int i = 0; i < arr.size(); i++) {
        temp = incl;
        incl = max(arr[i]+excl, temp);
        excl = temp;
    }
    return max(incl, excl);
    
    32|
    Permalink
Load more conversations

Need Help?


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