[Lesson 9][Maximum slice problem] MaxDoubleSliceSum

app.codility.com/programmers/lessons/9-maximum_slice_problem/max_double_slice_sum/

MaxDoubleSliceSum coding task - Learn to Code - Codility

# (i, mid, j) => 구간합의 최대값 찾기

def solution(A):
    N = len(A)
    l_best = [0] * N
    r_best = [0] * N

    for i in range(1, N - 1):
        l_best[i] = max(l_best[i - 1] + A[i], 0)

    for j in range(N - 2, 0, -1):
        r_best[j] = max(r_best[j + 1] + A[j], 0)

    # l_best: [0, 2, 8, 7, 11, 16, 15, 0]
    # r_best: [0, 16, 14, 8, 9, 5, 0, 0]

    rst = 0
    for mid in range(1, N - 1):
        rst = max(rst, l_best[mid - 1] + r_best[mid + 1])
    return rst


print(solution([3, 2, 6, -1, 4, 5, -1, 2]))  # 17