최대 부분합

다음 코드는 수열의 연속된 부분의 합 중 최댓값을 출력한다. 결과는 옳지만 N 이 커지면 시간 초과가 난다. 같은 결과를 시간 제한 안에서 출력하라.

n = int(input())
arr = list(map(int, input().split()))
best = arr[0]
for i in range(n):
    for j in range(i, n):
        s = sum(arr[i:j+1])
        if s > best:
            best = s
print(best)