Created
February 8, 2017 23:04
-
-
Save balazsnemeth/1e8fbdad6fd286315b1b0485908ae8e5 to your computer and use it in GitHub Desktop.
JS - NumberSolitaire - Dynamic Programming -
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// In a given array, find the subset of maximal sum in which the distance between consecutive elements is at most 6. | |
// https://codility.com/programmers/lessons/17-dynamic_programming/number_solitaire/ | |
// 100% for both performance & correctness | |
function solution(A) { | |
// The basic idea: | |
// We can compute the best sum of "i" (t[i]) based on the previous best sums! | |
// So let's store the best sum for each element "i" in this array: | |
const t = []; | |
function getmax(array) { | |
return Math.max.apply(null, array); | |
}; | |
for (let i = 0; i < A.length; i++) { | |
if (i === 0) { | |
t[0] = A[0]; | |
} | |
else { | |
// Get the most optimal choice from the previous 6 possible steps/options! | |
t[i] = getmax(t.slice(Math.max(0,i-6), i)) + A[i]; | |
} | |
} | |
return t[A.length - 1]; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment