acmicpc.net - 7476 - 최대 공통 증가 수열

https://www.acmicpc.net/problem/7476/

최대 공통 수열이 아니다.
최대 공통 증가 수열이다.

최대 공통 수열과 같이 DP로 풀면 되지만.
조금 고려해줘야 하는 것들이 있다.

최대 공통 수열에서는 'a[i] == b[j]' 일때 'dynamic[i][j] = dynamic[i][j - 1] + 1' 로 계산해주면 되지만.
최대 공통 증가 수열에서는 'a[i] == b[j]' 일때 dynamic[i][j] = (k:0 ~ j-1) if (b[k] < b[j]) 인 max(dynamic[i][k]) + 1 이다.

다시 정리하자면

a[i] == b[j] 일때 수열b에서 b[j]보다 작은 b[k]중 dynamic[i][k] 가 가장 큰 값을 가져오면 된다.

최종적으로 길이를 구할때도 dynamic[N][1~M] 을 확인하여 제일 큰 값을 가져오면 된다.