728x90
반응형
문제 출처: https://www.acmicpc.net/problem/1912
1912번: 연속합
첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.
www.acmicpc.net
풀이:
import sys
n = int(input())
lst = list(map(int,(input().split(' '))))
for i in range(1, n):
lst[i] = max(lst[i], lst[i] + lst[i-1])
print(max(lst))
lst[i] = max(lst[i], lst[i] + lst[i-1]
lst[i] 이전까지 계산해온 값중 최댓값을 계속저장함
lst[i] + lst[i-1] 이전까지 계산해온 최댓값 + 현재 값을 더해봄
max(lst[i], lst[i] + lst[i-1] 그 중 큰 값을 max로해서
lst[i] 최댓값 업데이트반응형
댓글