https://app.codility.com/programmers/lessons/9-maximum_slice_problem/max_double_slice_sum/
문제 분석
주어진 배열에서 최대가 되는 부분합을 찾아야 한다.
이때 조건으로 X, Y, Z 3개의 범위를 고려해야 한다.
X보다 큰 범위이어야 한다.
Y는 제외해야 한다.
Z보다 작은 범위이어야 한다.
`DoubleSlice의 합: A[X + 1] + A[X + 2] + ... + A[Y − 1] + A[Y + 1] + A[Y + 2] + ... + A[Z − 1]`
접근
head: 왼쪽 -> 오른쪽 방향의 부분합 / tail: 오른쪽 -> 왼쪽 방향의 부분합을 구함.
Y를 기준으로 head[i-1] + tail[i+1]의 최댓값을 구함.
A = [3, 2, 6, -1, 4, 5, -1, 2]일 때 두 배열의 누적합을 구하면 다음과 같다.
head = [0, 2, 8 7, 11, 16, 15, 0]
tail = [0, 16, 14, 8, 9, 5, 0, 0]
위 두 배열을 Y를 기준으로 head[i-1] + tail[i + 1]이 최대가 되는 값을 구하면,
Y를 기준으로 왼쪽 배열의 최대 부분합 + 오른쪽 배열의 최대 부분합을 구하는 것과 같다.
풀이
def solution(A):
if len(A) == 3:
return 0
head = [0] * len(A)
tail = [0] * len(A)
for i in range(1, len(A) - 1):
head[i] = max(0, head[i - 1] + A[i])
for i in range(len(A)-2, 0, -1):
tail[i] = max(0, tail[i + 1] + A[i])
max_sum = 0
for i in range(1, len(A) - 1):
max_sum = max(max_sum, head[i - 1] + tail[i + 1])
return max_sum
참고
https://jaejade.tistory.com/121
https://gets-better.tistory.com/m/9
https://sustainable-dev.tistory.com/25