# optimized O(N) solution
def sol(nums):
    ret = 0
    ma = 0
    n = len(nums)
    nums.reverse()
    for i,el in enumerate(nums):
        if i != n - 1:
            ma = max(ma, el)
            ret += ma
    return ret

# slower O(N^2) dp solution for testing
from functools import lru_cache
def dp(nums):
    n = len(nums)

    @lru_cache(None)
    def dfs(i):
        if i == 0:
            return 0
        else:
            score = ret = 0
            for j in range(i - 1, -1, -1):
                score += nums[i]
                ret = max(ret, score + dfs(j))
            return ret

    return dfs(n - 1)

# randomized tests
N = 100
L = 400
V = 100
from random import randint
for _ in range(N):
    l = randint(1, L)
    a = [randint(1, V) for _ in range(l)]

    actual = dp(a)
    mine = sol(a)

    if mine != actual:
        print(a)
        print(mine, actual)
        break