[백준_1912] 연속합 python

처음에 dp정의 자체를 잘못 설정했다.

처음 내 아이디어는 dp[i]를 i번째까지 최대 연속 합으로 설정하였으나,

이중for문에 걸려 시간 초과 문제가 발생했다.

 

이후 구글링을 통해 다른 아이디어를 찾아보니

dp[i]를 i번째까지 왔을 때, arr[i]와 dp[i-1] + arr[i] 중 최댓값으로 설정하는 정의를 통해 해결하는 방법을 찾았다.

처음엔 잘 이해가 가지 않았으나,

찬찬히 생각해보니 이와 같이 dp를 채우고 나중에 출력 시 전체에 max값을 출력 해 주면 되는 것이였다.

# n 입력

n = int(input())

# arr 입력

arr = list(map(int, input().split()))

# dp 설계

dp = [

　0 for _ in range(n)

]

# 초기설정

dp[0] = arr[0]

# dp 채워넣기

for i in range(1, n):

　dp[i] = max(arr[i], dp[i-1] + arr[i])

# 출력

print(max(dp))