kesarossss   2년 전

스택에 계속 쌓으며 갱신하면서 가장 긴 수열을 max에 저장해놓는 방식인데 반례를 도저히 찾을 수 없었습니다

틀리려면 max의 값을 갱신하기 때문에 삭제한 max가 가장 긴 부분수열의 부분이 되어여하는데 

즉, 나중에 추가될 원소들이 기존 max에는 달리지만 새로 갱신된 max에는 달리지 않는다는 건데

새로 갱신된 max의 마지막 원소의 값 > 나중에 추가될 원소의 최소값 > 기존 max의 마지막 원소의 값 

그런데 두 개의 max의 마지막 원소의 값은 같거나 기존 max가 크기 때문에 성립이 안되네요

그래서 틀릴 경우가 없다고 생각했는데... 틀렸습니다가 떳습니다.

kesarossss   2년 전

11

10 15 20 17 15 16 15 17 18 18 19

아 이게 있네 ㅋㅋ 머슥;;

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