[백준, 파이썬, 1912번] 연속합

 

풀이

 

• 초기 생각한 방법은 아래 두 번째 코드처럼 각 위치에서
• 슬라이싱한 값 까지의 합 중 가장 큰 값을 출력하고자 했지만 
• 2% 에서 시간 초과 발생
• 그래서 dp를 활용한 문제 해결을 위해 
• 현재 위치 전까지의 가장 큰 값(이전 dp값) + 현재 위치의 배열 값과
• 현재 배열의 값 중 큰 값을 현재 dp의 값에 저장하여
• 최종적으로 가장 큰 값을 출력하여 해결! 

 

정답 코드

import sys

input = sys.stdin.readline

n = int(input())

li = list(map(int,input().rstrip('\n').split()))

dp = [0]*n

dp[0] = li[0]

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

print(max(dp))

 

 

시간 초과 코드

import sys

input = sys.stdin.readline

n = int(input())

li = list(map(int,input().rstrip('\n').split()))

result = -sys.maxsize

for i in range(n):

    for j in range(i+1,n):

        val = sum(li[i:j])

        result = max(val,result)

print(result)