다이나믹 프로그래밍 문제 5 . 5

 

 

 

LIS 알고리즘

 

 

 

D[i] 는  array[i] 를 마지막 원소로 가지는 부분 수열의 최대 길이이다.

 

 

 

각각의 원소 하나만 이용해서 수열을 만든다 하면 그 길이는 1이기 때문에 1로 초기화

 

 

 

입력을 역순으로 뒤집고 LIS 알고리즘을 수행해서 정답을 도출한다

 

 

 

 

각각의 원소 하나만 이용해서 수열을 만든다 하면 그 길이는 1이기 때문에 1로 초기화

문자열을 역순으로 바꾸는 함수
파이썬은 array.reverse()
C++ 은 reverse(array.begin() , array.end()) ,  자바는 Collections.reverse(array) 이다

파이썬 max함수는 몇 개가 들어오든 거의 다 감당 가능하고
C++ max 함수와  자바 Math.max 함수는 2개만 비교 가능해서 코드의 마지막이 살짝 다르다