배열에서 이어진 구간 하나를 골라 합이 가장 크게 하는 문제다. 음수가 섞여 있어서 전부 더하는 게 답이 아니다.
모든 구간 더해보기
arr = [5, -3, 1, 7, -2]
ans = float('-inf')
for i in range(len(arr)):
cur = 0
for j in range(i, len(arr)):
cur += arr[j]
ans = max(ans, cur)
시작점을 고정하고 끝점을 늘려간다. 늘릴 때마다 원소 하나만 더하면 되므로 구간 합을 매번 다시 계산하지는 않는다. 그래도 구간의 개수만큼은 돌아야 한다.
끝점만 생각하기
구간을 두 점으로 보지 않고 끝점 하나로 본다. i 에서 끝나는 구간 중 합이 가장 큰 것을 안다면, i+1 에서 끝나는 구간의 답은 둘 중 하나다.
- 앞의 구간을 이어받고
arr[i+1]을 붙인 것 arr[i+1]하나로 새로 시작한 것
앞까지의 합이 음수면 이어받는 게 손해라 새로 시작하는 쪽이 이긴다.
arr = [5, -3, 1, 7, -2]
for i in range(1, len(arr)):
arr[i] = max(arr[i], arr[i] + arr[i - 1])
print(max(arr))
arr[i] 를 덮어쓴다. 갱신이 끝나면 arr[i] 는 원래 값이 아니라 "i 에서 끝나는 구간의 최대 합"이 된다.
[5, -3, 1, 7, -2] -> [5, 2, 3, 10, 8]
두 번째 칸이 -3 에서 2 가 된 건 앞의 5를 이어받았기 때문이고, 세 번째가 3 인 건 앞의 2를 이어받은 것이다. 마지막에 max 로 어느 끝점이 가장 큰지 고르면 10이 나온다.
덮어쓰기의 대가
별도의 dp 배열을 두지 않아서 짧다. 대신 원본이 사라진다.
이 문제는 답이 합 하나라 상관없었다. 구간의 시작과 끝을 알아야 하거나 원본을 뒤에서 다시 봐야 하면 덮어쓰면 안 된다.
앞의 완전탐색 셀에는 if cur > ans: 를 쓰다 만 자국이 그대로 남아 있다. 구간 위치를 같이 기록하려다 그냥 max 로 되돌린 것으로 보인다.