[백준 1912번] 연속합 (Python/파이썬)

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

1912번: 연속합

문제 유형은 Dp라고 되어있지만 내가 아직 Dp를 잘 몰라서 그런지 내가 Dp로 풀었는지 잘 모르겠다.

문제를 읽으면 Dp냄새가 술술 나긴 하는데 그냥 문제 읽고 구현했는데 풀렸다.

 

코드를 보면 배열 앞에서부터 합을 저장해 나가다가 음수로 빠지면 합을 0으로 바꾼다.

그리고 합이 최대값보다 커지면 최대값을 합으로 바꿔준다.

위의 과정을 배열을 한번 훑으면서 진행하면 연속합중에서 가장 큰 합이 나온다.

코드는 다음과 같다.

 

import sys
input = sys.stdin.readline
n = int(input())
sequence = list(map(int,input().split()))
##최댓값 변수
maximum = sequence[0]
##연속합을 저장해나갈 변수
tmp = 0
for i in range(n):
  tmp += sequence[i]
  maximum = max(maximum,tmp)
  ##연속합이 음수가 되면 연속합을 0으로 바꾼다.(음수는 더해봤자 작아지기 때문에 저장해나갈 필요가 없다.)
  if tmp < 0:
    tmp = 0
print(maximum)