gkfkagkfka12   2년 전

가장 긴 증가하는 부분 수열 + 해당 수열이 끝난 인덱스부터 가장 긴 감소하는 부분 수열 -1로 풀었고

예제를 비롯해 게시판에 있는 모든 반례까지 맞는데 어디가 틀린지 모르겠습니다.

찾아주시면 감사하겠습니다.

djm03178   2년 전

가장 긴 증가하는 부분 수열의 끝에서 시작하는 것이 최적일까요?

아래 예시에서 가장 긴 증가하는 부분 수열은 1 2 3이지만, 3에서부터 다시 감소하는 부분 수열을 구해도 총 길이가 더 늘어나지 못합니다.

하지만 증가 부분을 1 5로 잡으면, 감소 부분은 5 4 3으로 잡을 수 있어 총 길이를 4로 만들 수 있습니다.

댓글을 작성하려면 로그인해야 합니다.