iwillalways   2년 전

많은 분들이 이미 올리신 질문이긴 한데, 답변을 봐도 왜 그렇게 되는지 이해가 안되어 질문합니다.


예제 입력2 입니다.

2 1 -4 3 4 -4 6 5 -5 1

질문 검색해보니, 위의 답이 14 가 나오는 이유는 부분 수열 3 4 -4 6 5 의 합으로 나온다고 하는데, 이 수열이 어떻게 나올 수 있죠?

4 다음 -4 는 되는데 왜 -4 다음 3 은 안되는지, 그리고, 6 다음 5 가 올 수 있다면, 왜 5 다음 -5 는 안되는지 모르겠습니다.

제가 '연속' 이라는 말을 이해하지 못하는 것 같아요. 위치 상 연속을 의미하는 것 같기는 한데, 4 다음 -4 가, 6 다음 5 가 된다는 걸 보면 꼭 오름차순은 아니어도 되는 것 같은데, 예제 입력3 의 답이 -1 인 것을 보면 그것도 아리송하고...

설명해주실 분 계실까요?

a99azaz   2년 전

위치상 연속이 맞습니다.

2 1 -4 (3 4 -4 6 5) -5 1      괄호부분 합 14

괄호 좌우로 -4나 -5를 넣으면 값이 낮아지기 때문에 연속된 수의 합이 가장 높을 때는 3 4 -4 6 5 입니다

10 -4 3 1 5 6 -35 (12 21) -1   합 33

(-1) -2 -3 -4 -5             합 -1

djm03178   2년 전

"4 다음 -4 는 되는데 왜 -4 다음 3 은 안되는지, 그리고, 6 다음 5 가 올 수 있다면, 왜 5 다음 -5 는 안되는지 모르겠습니다."

안 되는 것이 아니라, 해도 되지만 그렇게 하면 최적의 답이 나오지 않기 때문에 안 하는 것입니다. 그러한 경우를 고려해도 됩니다. 하지만 다른 경우에서 더 좋은 답이 나오기 때문에 결국 최종적으로 고르지 않게 될 뿐입니다.

iwillalways   2년 전

이제야 이해했습니다. 왜이리 한 번에 이해가 안되는 문제들이 많은지...

답변 감사합니다.

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