wodhks6621   5년 전

dp[i]는 i번째 항까지의 가장 큰 증가 부분 수열의 합이라 설정하였습니다.

예제 출력은 잘되는데, 제출하니 반례가 있는건지... 틀렸다고 합니다.

로직은 1부터 i까지 진행하면서 a[i]가 (a[]는 입력받는 수열) a[j] (j < i)보다 크면 쭉 더하는 것입니다.

반례가 무엇인지 모르겠습니다.

djm03178   5년 전

단순히 수가 작다고 더하면 되는 건 아닙니다. 더한 수들 전체가 증가 수열을 이룬다고 보장할 수 없습니다.

https://ideone.com/8gpbXd

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