algorithm
가장 길게 증가하는 서브 시퀀스

가장 긴 하위 시퀀스 기본 정보

가장 길게 증가 하는 서브 시퀀스 문제는 서브 시퀀스의 요소가 가장 낮은 순서에서 가장 높은 순서로 정렬되는 주어진 입력 시퀀스에서 서브 시퀀스를 찾는 것입니다. 모든 서브 시퀀스는 인접하거나 고유하지 않습니다.

가장 길게 증가하는 서브 시퀀스의 적용 :

Longest Increasing Subsequence, Longest Common Subsequence와 같은 알고리즘은 힘내 등의 버전 관리 시스템에서 사용됩니다.

간단한 형태의 알고리즘 :

1. 두 문서에 공통된 고유 한 행을 찾습니다.
2. 첫 번째 문서에서 그러한 모든 줄을 가져 와서 두 번째 문서의 모양에 따라 순서를 정하십시오.
3. 결과 시퀀스의 LIS ( 인내 정렬 을 수행하여)를 계산하여 두 문서의 라인 사이의 일치 인 가장 길게 일치하는 일련의 라인을 가져옵니다.
4. 이미 일치 한 라인 사이의 각 라인 범위에서 알고리즘을 재실행하십시오.

이제 LCS 문제의 더 간단한 예를 살펴 보겠습니다. 여기서 입력은 뚜렷한 정수 a1,a2,...,an. 의 한 시퀀스입니다 a1,a2,...,an. , 우리는 그것에서 가장 길게 증가하는 서브 시퀀스를 찾고 싶습니다. 입력 7,3,8,4,2,6 경우, 예를 들어, 다음 긴 시퀀스가 증가 3,4,6-이다.

가장 쉬운 방법은 입력 요소를 오름차순으로 정렬하고 원래 및 정렬 된 시퀀스에 LCS 알고리즘을 적용하는 것입니다. 그러나 결과 배열을 보면 많은 값이 같고 배열이 매우 반복적으로 보입니다. 이는 LIS (longest increase subsequence) 문제가 1 차원 배열을 사용하는 동적 프로그래밍 알고리즘으로 수행 될 수 있음을 제시합니다.

의사 코드 :

1. 우리가 계산하고자하는 값의 배열을 기술하십시오.
   1 <= i <= n , 가장 길게 증가하는 입력 시퀀스의 길이를 A (i) 라고 합니다. 우리가 궁극적으로 관심을 갖는 길이는 max{A(i)|1 ≤ i ≤ n} 이다.
2. 재발을주십시오.
   1 <= i <= n 일 때 A(i) = 1 + max{A(j)|1 ≤ j < i 그리고 input(j) < input(i)}.
3. A.의 값을 계산하십시오.
4. 최적의 솔루션을 찾으십시오.

다음 프로그램은 A를 사용하여 최적의 솔루션을 계산합니다. 첫 번째 부분은 A (m) 이 입력의 최적 증가 부분 시퀀스의 길이가되도록 값 m을 계산합니다. 두 번째 부분은 최적의 증가하는 서브 시퀀스를 계산하지만 편의상 역순으로 출력합니다. 이 프로그램은 시간 O (n)에서 실행되므로 전체 알고리즘은 시간 O (n ^ 2)에서 실행됩니다.

1 부:

m ← 1 
for i : 2..n 
    if A(i) > A(m) then 
        m ← i 
    end if 
end for

2 부:

put a
while A(m) > 1 do 
    i ← m−1 
    while not(ai < am and A(i) = A(m)−1) do 
        i ← i−1 
    end while 
    m ← i 
    put a
 end while

재귀 적 솔루션 :

접근법 1 :

LIS(A[1..n]):
    if (n = 0) then return 0
    m = LIS(A[1..(n − 1)])
    B is subsequence of A[1..(n − 1)] with only elements less than a[n]
    (* let h be size of B, h ≤ n-1 *)
    m = max(m, 1 + LIS(B[1..h]))
    Output m

접근법 1의 시간 복잡도 : O(n*2^n)

접근법 2 :

LIS(A[1..n], x):
    if (n = 0) then return 0
    m = LIS(A[1..(n − 1)], x)
    if (A[n] < x) then
        m = max(m, 1 + LIS(A[1..(n − 1)], A[n]))
    Output m

MAIN(A[1..n]):
    return LIS(A[1..n], ∞)

접근법 2의 시간 복잡도 : O(n^2)

접근법 3 :

LIS(A[1..n]):
    if (n = 0) return 0
    m = 1
    for i = 1 to n − 1 do
        if (A[i] < A[n]) then
            m = max(m, 1 + LIS(A[1..i]))
    return m

MAIN(A[1..n]):
    return LIS(A[1..i])

접근법 3의 시간 복잡성 : O(n^2)

반복 알고리즘 :

값을 상향식으로 반복하여 계산합니다.

LIS(A[1..n]):
    Array L[1..n]
    (* L[i] = value of LIS ending(A[1..i]) *)
    for i = 1 to n do
        L[i] = 1
        for j = 1 to i − 1 do
            if (A[j] < A[i]) do
                L[i] = max(L[i], 1 + L[j])
    return L

MAIN(A[1..n]):
    L = LIS(A[1..n])
        return the maximum value in L

반복적 접근법의 시간 복잡도 : O(n^2)

보조 공간 : O(n)

{0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15} 을 입력으로 사용할 수 있습니다. 따라서 주어진 입력에 대한 가장 긴 Increasing Subsequence는 {0, 2, 6, 9, 11, 15} 입니다.

C # 구현

public class LongestIncreasingSubsequence
{
    private static int Lis(int[] input, int n)
    {
        int[] lis = new int[n];
        int max = 0;
        for(int i = 0; i < n; i++)
        {
            lis[i] = 1;
        }
        for (int i = 1; i < n; i++)
        {
            for (int j = 0; j < i; j++)
            {
                if (input[i] > input[j] && lis[i] < lis[j] + 1)
                    lis[i] = lis[j] + 1;
            }
        }
        for (int i = 0; i < n; i++)
        {
            if (max < lis[i])
                max = lis[i];
        }
        return max;
    }

    public static int Main(int[] input)
    {
        int n = input.Length;
        return Lis(input, n);
    }
}