https://www.acmicpc.net/problem/1912
1912번: 연속합
첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.
www.acmicpc.net
# 2023.01.04
import sys
input = sys.stdin.readline
n = int(input())
number = list(map(int, input().split()))
dp = [0]*(n)
dp[0]=number[0]
for i in range(1, n):
dp[i]+=(max(dp[i-1], 0)+number[i])
print(max(dp))dp table을 이용
dp[i]의 값에 연속합을 저장
dp[i]에 "dp[i-1]을 더하는 것 or 포함하지 않는 것" 둘 중 더 큰 값을 저장함
최종 답은 dp table의 가장 큰 값을 출력하면 됨
'Problem Solving > BOJ' 카테고리의 다른 글
| [DP] 12865 평범한 배낭 (0) | 2023.01.04 |
|---|---|
| [Greedy] 1931 회의실 배정 (0) | 2023.01.04 |
| [Stack] 1874 스택 수열 (0) | 2023.01.03 |
| [Stack] 4949 균형잡힌 세상 (0) | 2023.01.03 |
| [Brute Force] 7568 덩치 (1) | 2023.01.03 |
