javascriptarrayschallenge-response

Biggest sum from array without adding 2 consecutive value


I'm working on a challenge from codefights.com.
Given an array of integer (possibly negative) I need to return the biggest sum I can achieve without adding two consecutive integer (I can't change the order of the array).

Not easy to explain so here's a few examples:

I though I had it with this code :

function solve(vals) {
  var even=0; var odd=0;
  for(var i=0; i<vals.length; i++){
    if(i%2==0){
      even+=vals[i];
    } else {
      odd+=vals[i];
    }
  }
  return Math.max(even, odd);
}

But then I got this testcase: [1,0,0,3] where it should return 4, skipping the two '0' which made me realize I've been looking at it all wrong.
And now I'm stuck, don't really know how to do it.

Any ideas ?

edit:

Using MrGreen's answer I got this:

function target_game(a) {
    var dp=[], l=a.length-1;
    dp[0]=a[0];
    dp[1]=Math.max(a[0],a[1]);

    for(var i=2; i<=a.length-1; i++){
        dp[i]=Math.max(dp[i - 1], dp[i - 2] + a[i]);
    }

    return dp[l];
}

Which works fine unless the array contains negative value.
This input: [-1,0,1,-1] returns 0. I'm still working on a fix but I'm editing the question to have a bullet proof solution :p


Solution

  • This is a classical dynamic programming problem.

    Define dp[i] to be the maximum sum we can get if we consider the elements from 0 to i.

    Then dp[i] = max(dp[i - 1], dp[i - 2] + a[i])

    The intuition behind this, if you takea[i] in the sum then you cannot take a[i - 1]

    Base cases: dp[0] = max(0, a[0]) and dp[1] = max(0, a[0], a[1])

    You can check this lesson:

    part-1 part-2 part-3 part-4