[Python] 1912번 연속합

✏️ 문제

 

문제 파악

처음에 이중 반복문 써서 풀고 있다가.. 시간 초과나서 찾아보니 최대 부분합을 푸는 방법 중 카데인 알고리즘을 써야 풀리는 문제였다.

간단하게 설명하자면 시작 원소를 기준으로 부분 배열을 구하는 게 아니라 끝 원소를 기준으로 모든 부분 배열을 구하는 알고리즘이다. 

 

 

알고리즘

• 다이나믹 프로그래밍 

 

 

코드

• 시간 초과 코드

import sys
input = sys.stdin.readline

n = int(input())
ary = list(map(int, input().split())) 
value = -1000

for i in range(n):
  temp = ary[i]
  for j in range(i+1, n): 
    value = max(value, temp)
    temp += ary[j]

print(value)

• 통과 코드

n = int(input())
ary = list(map(int, input().split())) 
current_sum = -1000
max_sum = -1000

for i in range(n):
  current_sum = max(ary[i], current_sum + ary[i])
  max_sum = max(max_sum, current_sum)

print(max_sum)