Algorithm/구현

[백준] 1912번 연속합

HANNI하니 2023. 10. 23. 18:51

사용 언어 - Python3

문제 -  1912번 연속합

 

1912번: 연속합

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

www.acmicpc.net

 

정답

누적된 숫자들의 합 기억하기 (정답 맞춘 여부 X)

컴퓨터에게 기억하는 방법 알려주기

1. prefix라는 누적합 배열 생성

2. 값이 너무 작아지면, 기존의 값 무시하고 새로 시작하기

max(prefix[i] + arr[i], arr[i])

3. 최대값 구하기

 

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int,input().split()))
prefix = [-1001]*(n+1)

for i in range(n):
    prefix[i+1] = max(prefix[i] + arr[i], arr[i])
print(max(prefix))

 

 

레퍼런스

  • 정답 깃허브

https://github.com/yyeongeun/codingtest/blob/main/BAEKJOON/1912_%EC%97%B0%EC%86%8D%ED%95%A9.py