문제

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

나의 코드

"""
1. 아이디어
DP에 값을 초기화 해준 다음 현재 숫자와 이전까지의 누적합을 비교해서 큰 값을 DP에 넣는식으로 
작성하면 된다.

2. 시간복잡도
O(N) - 두번째 반복문은 사실상 1번만 돌기 때문에 의미가 없고 MAX또한 2개의 값만 비교하는 것이므
로 무시해도 된다.
"""

from sys import stdin
input = stdin.readline

n = int(input())
nums = list(map(int, input().split()))
dp = [0] * n

for i in range(n):
    dp[i] = nums[i] # dp값을 이렇게 초기화 해준 이유는 예시 3번에 -1이 답으로 나올려면 dp자체에 nums값이 있어야 한다.
    for j in range(i-1, i): # i-1을 안해주면 시간초과남. 사실상 이전 값하고만 비교하면 되기 때문에 i-1만 해줘도 된다.
        dp[i] = max(nums[i], dp[j]+nums[i])

print(max(dp))
    

다른 풀이 코드

from sys import stdin
input = stdin.readline

n = int(input())
num = list(map(int, input().split()))

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

print(max(num))

느낀점

DP문제 풀기전에 항상 식을 써보고 작성하는 습관 들이기 ㅇㅇ!