그랬었습니다

https://everyyy.tistory.com/75 [백준]11053-가장 긴 증가하는 부분 수열(Dynamic Programming) 이 문제 역시 동적 계획법으로 푸는 문제다. 주어진 수열에서 일정 부분을 뽑아 가장 긴 증가수열을 만들고, 그 길이를 구하는 문제다. 이 문제에는 가장 심플한 규칙이 있다. v[i][0]이 i번째 수의 값이고, v[i].. everyyy.tistory.com 11053번 가장 긴 증가하는 부분 수열 문제와 매우 흡사하고, 위 문제를 조금만 변형해면 풀 수 있는 문제이다. 우선 똑같이 가장 긴 증가하는 부분 수열을 구한다. 동시에 오른쪽에서 왼쪽으로 가면서 가장 긴 감소하는 부분 수열을 구한다. 왼쪽에서 오른쪽으로 이동하며 반환할 후보 변수에 일단 증가, 감소 중 더 ..