Biggest sum from array without adding 2 consecutive value

Question

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:

input: [1, 2, 3, 4]: you're gonna pass the '1', take 2, can't take 3, take 4 and you get 6.
input: [1, 3, 1]: pass the '1', take 3 and you can't take 1 so you have 3.

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

because you want the biggest sum possible and you can't add 2 consecutive value from the array. Skipping the ones lets you achieve the biggest sum by adding 2 and 4 (1st example). — Spare
– Spare, Commented Jul 23, 2015 at 9:10

MrGreen · Accepted Answer · 2015-07-23 12:32:20Z

4

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

edited Jul 23, 2015 at 12:32

answered Jul 23, 2015 at 9:11

MrGreen

4994 silver badges24 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Spare Over a year ago

Thanks, watching the video now :)

Spare Over a year ago

As it turns out there might be negative value in the array which throw off what I did using your answer. Editing my question now.

MrGreen Over a year ago

I think if we change the base cases, the solution would work for negative numbers. Check my updated post

Spare Over a year ago

Working on something else right now but I'll check it out later. Thanks for the update !

Spare · Accepted Answer · 2015-07-24 07:41:47Z

0

Here is the "best" answer from the challenge (shortest actually):

function solve(a) {
  b = t = 0
  for (i in a) {
    c = b + a[i]
    b = t
    t = c > t ? c : t
  }
  return t
}

Here is a version where I renamed the variables to make it more understandable:

function solve(vals) {
  prevTotal = total = 0
  for (i in vals) {
    alt = prevTotal + vals[i]
    prevTotal = total
    total = alt > total ? alt : total
  }
  return total
}

answered Jul 24, 2015 at 7:41

Spare

828 bronze badges

Collectives™ on Stack Overflow

Biggest sum from array without adding 2 consecutive value

2 Answers 2

4 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related