[백준] 1912 - 연속합 Python

https://www.acmicpc.net/problem/1912

1912번: 연속합

(1) 첫번째 코드 - 메모리 초과

import sys

input = sys.stdin.readline

N = int(input())
num = list(map(int, input().split(" ")))
M = len(num)
dp = [[-1000] * (M) for _ in range(M)]
answer = -1000

# print(num)

for i in range(M):
    for j in range(M):
        if i == j:
            dp[i][j] = num[j]
        elif i > j:
            continue
        else:
            dp[i][j] = dp[i][j - 1] + num[j]

for i in range(M):
    answer = max(answer, max(dp[i]))

print(answer)

이차원 배열로 풀었는데, 메모리 초과가 두번이나 나서 일차원 배열을 사용해야함을 깨달았다. 

 

(2) 두번째 코드 - 성공

import sys

input = sys.stdin.readline

N = int(input())
num = list(map(int, input().split(" ")))
M = len(num)
dp = [-1000] * (M)

dp[0] = num[0]

for i in range(1, M):
    dp[i] = max(dp[i - 1] + num[i], num[i])

print(max(dp))