[알고리즘/백준] 16198번 : 에너지 모으기(python)

구슬 하나를 없애고 양 옆 수를 곱해서 더하면서 풀면 된다.
백트래킹을 사용했다.
만약 길이가 2이면 두개를 곱하고 더 큰걸 저장한다.

def dfs(tmp):
    global ans
    if len(a) == 2:
        if ans < tmp:
            ans = tmp
        return
    else:
        for i in range(1, len(a) - 1):
            k = a[i]
            del a[i]
            dfs(tmp + a[i - 1] * a[i])
            a.insert(i, k)


N, a = int(input()), list(map(int, input().split()))
ans = 0
dfs(0)
print(ans)