Самая большая сумма из массива без добавления 2 последовательных значений

Question

Я работаю над вызовом с codefights.com.
Учитывая массив целых чисел (возможно, отрицательный), мне нужно вернуть самую большую сумму, которую я могу достичь, не добавляя два последовательных целого числа (я не могу изменить порядок массива).

Не легко объяснить, так вот несколько примеров:

• вход: [1, 2, 3, 4]: ты собираешься пройти '1', возьмите 2, не может принимать 3 , взять 4 и вы получите 6.
• вход: [1, 3, 1]: передать '1', возьмите 3, и вы не можете взять 1, так что вы имеете 3.

я, хотя я имел это значение с кодом:

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); 
} 

Но тогда я получил этот тестовый файл: [1,0,0,3], где он должен вернуться 4, пропустив два «0», которые заставили меня понять, что я смотрел на все это неправильно.
И теперь я застрял, не знаю, как это сделать.

Любые идеи?

редактировать:

Используя ответ Mrgreen, я получил это:

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]; 
} 

, который работает прекрасно, если массив не содержит отрицательное значение.
Этого вход: [-1,0,1, -1] возвращает 0. Я все еще работаю над исправлением, но я редактирую вопрос, чтобы иметь пуленепробиваемое решение: р

Answer 1

Это проблема классического динамического программирования.

Определить dp[i] как максимальную сумму, которую мы можем получить, если рассматривать элементы от 0 до i.

Тогда dp[i] = max(dp[i - 1], dp[i - 2] + a[i])

Интуиция за этим, если вы берете a[i] в сумме, то вы можете не принимать a[i - 1]

базовых случаев: dp[0] = max(0, a[0]) и dp[1] = max(0, a[0], a[1])

Вы можете проверить этот урок:

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

Answer 2

Вот «лучший» ответ от задачи (кратчайшее на самом деле):

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

Вот версия, где я переименовал переменные, чтобы сделать его более понятным:

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