[Algorithm]백준, 1912, 연속합

문제:www.acmicpc.net/problem/1912

 

비고:

-Dynamic programming

-예제2에서 문제 포인트를 알아차려야했는데 놓쳤다.

2 1 -4 3 4 -4 6 5 -5 1 에서 6 5->11이 답이라고 착각하였다. 답은 3 4 -4 6 5로 14다.

-여기서부터 문제를 파악하고 해결해 나가자.

-각 index마다 left max값과 right max값 그리고 index에서의 값을 다 더하고 취합하고 취합한 것에서 max를 구하면 된다.

-각 점마다 left max를 dictionary로 박자. 이 때, index가 작은 순부터 left max를 구하는 것에서 dynamic programming

-0에서는 left max가 0, 1에서는 left max가 0에서의 leftmax + 0에서의 값, 이 때 이 더한 값이 음수면 1에서의 leftmax는 0, 양수면 그 값을 1에서의 left max로 택한다.

-이러면 n번의 계산으로 모든 점에서의 left max를 구한다.

-마찬가지로 n번의 계산으로 모든 점에서의 right max를 구한다.

-문제파악에서 차질이 생겼다. 다음에는 반드시 예제의 정답을 믿자. 예제가 틀렸다고 생각하다니...ㅉㅉ

-게다가 사람들이 많이 푼 문제에 오류가 있다고 생각하면 되겠냐

-난이도중

 

내소스코드:

boj.kr/12104c7b668241f7b7ef8ee4d6ab8541

공유 소스 보기