[알고리즘] LIS (최장 증가 수열)

백준의 11053번 , 11054번, 2565번을 풀다가 '최장 증가 수열'의 코드를 정리해야겠다고 생각이 들어서 정리한다.

 

//최장 증가 수열 정리 코드.
#include <stdio.h>

int a[1000][2];
int N;
int max;

int main() {
    int i, j;
    scanf("%d", &N);
    
    for(i = 0; i < N; i++)
        scanf("%d", &a[i][0]);
    
    
    for(i = 0; i < N; i++) {
        for(j = 0; j < i; j++) {
            if(a[i][0] > a[j][0] && a[i][1] < a[j][1])
                a[i][1] = a[j][1];
        }
        a[i][1]++; // 수열에 나 포함(맨앞자리 시작했을때 기본값 역할도 해줌.)
        if(max < a[i][1])
            max = a[i][1];
    }
    
    printf("%d", max);

}

예제 입력 :

6

10 20 10 30 20 50

출력

4

 

 

 

필요하다면, 이해 그림 참고

wootool.tistory.com/96