백준 11053 / 가장 긴 증가하는 부분 수열

이거 꽤 중요하다고 한다.

LIS (Longest Increasing Subsequence)라고 따로 명칭이 있는 알고리즘이다.

풀이법은 입력된 수열에서의 비교와

새로운 배열을 하나 생성해 

그 수가 몇번 째에 놓일 수 있는지, 두가지 비교를 하는 것이다.

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

예를들어

2, 1, 2 이렇게 3개의 수가 있다고 가정하면

첫번쨰 수 2는 생성될 부분 수열의 첫번째에 놓일수 있으니

D[0] = 1이다.

두번째 수 1 또한 생성될 부분 수열의 첫번쨰에 놓일수 있으니

D[1] = 1이다.

그리고 첫번쨰 수 2의 뒤에 놓일 수 없기떄문에 그래로 1.

세번 쨰 수 2는 우선, 생성될 부분 수열의 첫번째에 놓일 수 있으니 D[2]=1이다.

또한 두번째 수인 1의 뒤에 놓일 수 있으니 D[1]에서 1을 더해준 2가 된다.

첫번째 수인 2의 뒤에는 놓일 수 없으니 무시.

이렇게 되면 배열 D의 값은

1, 1, 2 가 되므로 최대값인 2가 답이 된다.

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

긴 예를 들면 (5,1,4,2,7,6,3,9,2)

이렇게 되므로 최대값인 4가 답이 되는 것

코드는 

for (int i = 0; i < n; i++) {
        d[i] = 1;
        
        for (int j = 0; j < i; j++) {
            if (arr[j] < arr[i] && d[i] < d[j] + 1) {
                d[i] = d[j] + 1;
            }
 
        }
    }

점화식은

arr[j] < arr[i] 일떄,

d[i] = max(d[j]) +1