LA2 | Torneio 3 (2022/2023) | Duplica

'''
Optimize a seguinte função.
'''


def duplica(lista, dic={}):
    if len(lista) == 0:
        return 0
    if len(lista) == 1:
        return 2 * lista[0]

    if tuple(lista) in dic:
        return dic[tuple(lista)]

    a = lista[0] + duplica(lista[1:], dic)
    b = 2 * lista[0] + lista[1] + duplica(lista[2:], dic)
    res = max(a, b)
    dic[tuple(lista)] = res
    return res

Testes

# 1
lista = [5,1,3,4,5,3,1,3,3,5,5,1,2,3,4,5,1,3,4,5,3,1,3,3,5,5,1,2,3,4]
> Resultado = 149

# 2
lista = list(range(100))
> Resultado = 7450

# 1
lista = [5,3,2,4]
> Resultado = 23