쿠키 구입

• 구해야 할것은 문제에 다 주어져있다. sum(A[l:m]) == sum(A[m:r]) == X 인 X의 최대값이다.
• 이터레이션을 하는 방법에 따라 조금 더 공간복잡도를 효율적으로 쓰거나, 브랜치를 좀더 잘하거나 하는 방법이 있지만, 결국 시간 복잡도는 모든 구간에 대해서 구간합을 구해보는 O(n^2)이다.
• 아래 코드에서 구현한 방법은 식을 조금 바꿔쓴 뒤 prefix sum을 이용하도록 만든 방식으로, 딱히 효율적이지는 않지만 코드가 짧다.
  • sum(A[l:m])=sum(A[m:r]) 이라면 sum(A[:m])-sum(A[:l])=sum(A[:r])-sum(A[:m]) 이므로 2*sum[:m] = sum(A[:l])+sum(A[:r])이 된다.
  • 다시 말해서 어떤 x, y에 대해서, (sum(A[:x])+sum(A[:y]))/2 = sum[:z] 라면, 원하는 조건을 만족시키는 구간이 존재한다는 것이고 그 구간의 합은 sum(A[x:y])/2 = abs(sum(A[:x])-sum(A[:y]))/2 이다.
• 구현은 안했으나 공간복잡도 O(1)로 푸는 방법은, m에 대해서 이터레이트하면서, l과 r을 각각 반대쪽으로 번갈아서 이동시키면서 원하는 구간을 찾는 방법이다.

"""Solution code for "Programmers 49995. 쿠키 구입".

Using prefix sum.
- Problem link: https://programmers.co.kr/learn/courses/30/lessons/49995
- Solution link: http://www.teferi.net/ps/problems/programmers/49995
"""

import itertools


def solution(cookie):
    prefix_sums = set(itertools.accumulate([0] + cookie))
    return max((abs(x - y) // 2
                for x, y in itertools.combinations(prefix_sums, 2)
                if (x + y) % 2 == 0 and (x + y) // 2 in prefix_sums),
               default=0)