'가장 길게 증가하는 서브 시퀀스'문제를 해결하기위한 알고리즘을 설명하십시오.

Question

저는 지난 두 시간 동안이 알고리즘을 이해하려고 노력했지만 얻을 수는 없습니다. 이해할 수있는 방식으로 설명해주십시오. 그 최대 값이 현재 요소의 값보다 작게되도록 현재 요소 앞 요소의 긴 시퀀스의 한 길이만큼 증분으로 각 요소

function lis_length(a) 
    n := a.length 
    q := new Array(n) 
    for k from 0 to n: 
     max := 0; 
     for j from 0 to k, if a[k] > a[j]: 
      if q[j] > max, then set max = q[j]. 
     q[k] := max + 1; 
    max := 0 
    for i from 0 to n: 
     if q[i] > max, then set max = q[i]. 
    return max; 

Answer 1

첫 번째 (이중) 루프가 종료 된 후 q[i]은 i에서 끝나는 가장 긴 증가하는 서브 시퀀스의 길이입니다.

는 이중 루프가 어떻게 작동하는지 볼 q[j] 이미 위치 j에서 끝나는 가장 큰 증가 시퀀스의 길이를 포함한다고 가정하지만, 0 및 k-1 사이에 대해서만 j합니다. 이 점을 감안할 때 q[k]은 어떻게 계산합니까?

글쎄, 당신은 j < k와 a[j] < a[k]와 j 모두 찾을 것, 가장 큰했다 대응 q[j] 값을 확인할 하나를 추가하고, q[k]에 그 값을 숨기고. 이것은 내부 루프가하는 것과 정확히 같습니다.

따라서 내부 루프에 들어가기 전에 q[j]에는 0과 k-1 사이의 j에 대한 올바른 값이 이미 있습니다. 그리고 출구에서 k에 대한 올바른 값도 있습니다. 이중 루프가 종료 될 때까지 q[i]은 모두 i에 대해 0과 n 사이의 올바른 값을 갖습니다.

최종 루프는 그 중에서 가장 큰 루프를 선택합니다. 이는 대답입니다.

Answer 2

전류 소자로 만든 소자 긴 시퀀스의 수를 설정.

알고리즘은 양수의 배열을 취합니다 (요소가 0 이하일 수 없음).