0
125
ViewsHow to optimize recursion JavaScript
I am struggling with this codewars problem where I have to find the highest sum by selecting the card on the left or right. I managed to solve this using two recursive calls for each side respectively:
function solve(cards, i, j, sum, x)
{
if (i > j)
return sum;
var left = solve(cards, i+1, j, sum+(Math.pow(2,x)*cards[i]), x+1 );
var right = solve(cards, i, j-1, sum+(Math.pow(2,x)*cards[j]), x+1 );
return left > right ? left : right;
}
I created a diagram in PowerPoint to show how I see my code. It will be like a binary tree:
But the execution of my program is very very slow. Please show me how I can do this better.
·
Juan Pablo Isaza
1 answers
Answer question0
The faster solutions to this problem don't use recursion, they use Dynamic Programming where you store data that might be repeated multiple times if you use recursion. Using recursion, the execution time will increase exponentially with every added element to the card list. Here's a faster solution using Dynamic Programming.
function calc(cards){
let n = cards.length;
let dp = Array.from(Array(n), _ => Array(n).fill(0));
for (let i = 0; i < n; i++)
dp[0][i] = 2 * cards[i];
for (let i = 1; i < n; i++)
for (let j = 0; j < n - i; j++)
dp[i][j] = Math.max(dp[i - 1][j] * 2 + dp[0][i + j], dp[i - 1][j + 1] * 2 + dp[0][j]);
return dp[n - 1][0]
}
console.log(calc([1,2,5]))
console.log(calc([1]))
console.log(calc([1,1]))
console.log(calc([1,2,1]))
console.log(calc([4, 10, 2, 3, 1, 3, 1, 6, 9]))
·
Juan Pablo Isaza
Report
Answer question