oldbook   4년 전

i번째 배열이 부분수열의 가장 큰 숫자라 가정하고

1~ i-1 까지 배열의 값이 i번째 보다 작으면 모두 이 부분수열에 포함되므로

sum함수 다 더해줬습니다.

그렇게 1~n 까지 배열에 각각 구해줘서 max 출력해줬습니다.

뭐가 문제일까요 ㅜㅜ

ljh6274   4년 전

증가 부분 수열이기 때문에 1~i-1까지 모두 더 하면 안됩니다.

예를 들어 

10
1 100 55 50 60 3 5 6 7 8

의 경우에 질문자님 코드에선 1 + 55 + 50 + 60 = 166이 출력되지만

실제 가장 큰 증가 부분 수열은 1 + 55 + 60 으로 116이 정답 입니다.

다이나믹 프로그래밍 방식으로 하셔야 합니다.

d[i]를 i번째까지 최대 증가 부분 수열의 합으로 정의 하시고 이를 이용하시면 됩니다.

oldbook   4년 전

아하 !! 그렇군요 ~~!

감사합니다. 한수 배웠습니다.

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