https://www.acmicpc.net/problem/25049
문제 요약
- 설명을 잘 이해하면 부분합이 큰 두 개를 구하는 문제임
- 전체 합 + 부분합1 + 부분합2 의 최대를 구하는 문제인데, 부분합 끼리 겹치면 안됨
접근법
- 부분합 구하는 것은 알고 있는 방식으로 구하면 되는데
- 처음에 분할정복으로 접근했었음
- 부분합 두개가 큰 것을 분할해서 구해나가는데
- 중간에 걸친 것 처리가 매끄럽지 못해서 정답을 못구했음
- 에디토리얼을 참고했고, 너무 어렵게 생각했었음
- 특정 지점을 기준으로 왼쪽 부분합 최대값 + 오른쪽 부분합 최대값 방식으로 접근하면 되는 것이었음
newbieski