길이가 증가하는 서브 시퀀스 수

Question

시간 O (n k log (n))의 배열에서 길이 K의 증가하는 서브 시퀀스의 수를 나에게 알리는 알고리즘을 이해하려고합니다. O (k * n^2) 알고리즘을 사용하여이 동일한 문제를 해결하는 방법을 알고 있습니다. 나는이 솔루션이 BIT (Fenwick Tree)와 DP를 사용한다는 것을 발견했다. 나는 또한 일부 코드를 발견했지만, 나는 그것을 이해할 수 없었다.

내가 방문한 몇 가지 링크가 도움이되었습니다. 일부는 나를 도울 수 있다면 정말 감사하겠습니다

Here in SO
Topcoder forum
Random webpage

아웃이 알고리즘을 이해합니다.

Answer 1

나는 그것의 논리를 설명 here에서 내 알고리즘을 재현하고 있습니다 :

dp[i, j] = same as before num[i] = how many subsequences that end with i (element, not index this time) 
     have a certain length 

for i = 1 to n do dp[i, 1] = 1 

for p = 2 to k do // for each length this time num = {0} 

    for i = 2 to n do 
    // note: dp[1, p > 1] = 0 

    // how many that end with the previous element 
    // have length p - 1 
    num[ array[i - 1] ] += dp[i - 1, p - 1] *1* 

    // append the current element to all those smaller than it 
    // that end an increasing subsequence of length p - 1, 
    // creating an increasing subsequence of length p 
    for j = 1 to array[i] - 1 do *2*  
     dp[i, p] += num[j] 

당신은 세그먼트 나무 또는 이진 인덱스 트리를 사용하여 *1* 및 *2*을 최적화 할 수 있습니다. 이 효율적 num 어레이에서 다음 작업을 처리하기 위해 사용될 것이다 :

(x, v) 주어

• (*1* 동안 관련) vnum[x]에 추가;
• x이 있으면 num[1] + num[2] + ... + num[x] (*2*과 관련 있음)을 찾으십시오.

이것은 두 데이터 구조 모두에 대한 간단한 문제입니다.

참고 : 이것은 O(n*k*log S)의 복잡성을 갖습니다. 여기서 S은 배열의 값의 상한입니다. 이것은 충분히 좋을 수도 있고 그렇지 않을 수도 있습니다. O(n*k*log n)으로 만들려면 위 알고리즘을 실행하기 전에 배열의 값을 정규화해야합니다. 정규화는 모든 배열 값을 n보다 작거나 같은 값으로 변환하는 것을 의미합니다. 그래서이 :

5235 223 1000 40 40 

가된다 :

4 2 3 1 1 

이것은 일종의으로 수행 할 수 있습니다 (원래의 인덱스를 유지).