백준 1912번(python)

---

# 메모리 초과 코드
N = int(input())
num_list = list(map(int, input().split()))

dp = [[0] * (N) for _ in range(N + 1)]

for i in range(1, N):
    for j in range(i, N):
        dp[i][j] = max(num_list[j - 1] + num_list[j], dp[i][j - 1] + num_list[j])
        
max_value = -1001

for sub_dp in dp:
    if(max_value < max(sub_dp)):
        max_value = max(sub_dp)
print(max_value)

N = int(input())
num_list = list(map(int, input().split()))

dp = [0 for _ in range(N)]
dp[0] = num_list[0]
for i in range(1, N):
    # 위 코드는 첫 번째 경우는 논리에 맞지 않음.
    # case_1 : 현재 인덱스의 수 -> 반례 2, (-2, -1)
    # case_2 : 이전까지의 연속합과 현재 값을 더한 것
    dp[i] = max(num_list[i], dp[i - 1] + num_list[i])
        
print(max(dp))