spearkkk   1달 전

한 숫자를 제거해서 최대값을 구하는 문제인데, 

저는 우선 최대로 감소되는 부분을 찾아서 0으로 만들어주고 다시 최대합을 구했습니다.


10, -4, 3, 1, 5, 6, -35, 12, 21, -1 일 때, 각 자리에서 뒤의 숫자를 더한 최대합은 

21, 11, 15, 12, 11, 6, -2, 33, 21, -1 입니다. 

여기에서  증감량을 구하면

10, -4, 3, 1, 5, 8, -35, 12, 22 입니다.

최대로 감소되는 부분 -35인 부분을 제거하고

10, -4, 3, 1, 5, 6, 0(-35제거), 12, 21, -1 구하면 54가 나옵니다.

예제 답은 맞지만, 반례가 있는 거 같습니다.


제 방법이 틀렸을텐데, 어떻게 틀렸을까요?

zlzmsrhak   1달 전

제가 알고리즘을 이해한 게 맞다면,

6

20 -10 1 -50 2 -51 3

부분합 최대를 구하면,

20 -10 1 -50 2 -51 3

가장 많이 감소하는 구간인 -51을 0으로 만들면 답이 20이 나오고,

앞의 -10을 지우면 답이 21이 나옵니다.

spearkkk   1달 전

감사합니다 다시 생각해보겠습니다.

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