Самая длинная возрастающая подпоследовательность (Javascript) Facebook Algo - PullRequest
Новая
       24

Самая длинная возрастающая подпоследовательность (Javascript) Facebook Algo

0 голосов
/ 06 мая 2020

Я пытался решить эту проблему с возвратом вместо DP ... и столкнулся с проблемой, которая не имеет для меня смысла. вот мой код 

function solve(A) {
  let lp = 0;
  const path = [];

  const traverse = function (arr, i = 0) {
    if (i >= arr.length) return;
    for (j = i; j < arr.length; j++) {
      if (path.length === 0 || arr[j] > path[path.length - 1]) {
        path.push(arr[j]); 

// here is the problem I don't understand, I am calling the recursive function with( j + 1) 
// but somehow that reads it as j = j + 1; why is this happening? 
// I would understand if it was an Array where the j would pointing to memory but it shouldn't // happen to a regular number, right?  

        traverse(arr, j + 1);

// this causes the j variable in the for loop to increment by 1 so I can't get back track properly. 

        if (path.length > lp) lp = path.length;
        path.pop();
      } 
    }
  }

  traverse(A);
  return lp;
}

const A = [69, 54, 19, 51, 16, 54, 64, 89, 72, 40, 31, 43, 1, 11, 82, 65, 75, 67, 25, 98, 31, 77, 55, 88, 85, 76, 35, 101, 44, 74, 29, 94, 72, 39, 20, 24, 23, 66, 16, 95, 5, 17, 54, 89, 93, 10, 7, 88, 68, 10, 11, 22, 25, 50, 18, 59, 79, 87, 7, 49, 26, 96, 27, 19, 67, 35, 50, 10, 6, 48, 38, 28, 66, 94, 60, 27, 76, 4, 43, 66, 14, 8, 78, 72, 21, 56, 34, 90, 89]
const B = [1,3,4,2,5,3]

console.log(solve(A))
console.log(solve(B))

будет признателен за объяснение, заранее спасибо !!!

...