백준/문제풀이_python
1912 연속합 _ python
휴대용치즈
2022. 11. 28. 17:42
https://www.acmicpc.net/problem/1912
1912번: 연속합
첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.
www.acmicpc.net
어렵던데...
문제 접근
DP가 그렇듯... 생각못하면 어렵다.
순차적으로 더한 수중에 최대값을 찾는것.
그럼 처음부터 순차적으로 더해서 DP에 저장하면 된다.
저장해나가다가 합이 음수라면 다시 더해가면 된다.
-35를 계산하면 음수가 나오는데, 그다음인 12에선 앞에값을 무시하고 다시시작하면 된다.
그리고 이 계산을 마친 DP에서 최대값을 출력하면 끝.
코드
import sys
input = sys.stdin.readline
"""
"""
#입력
N = int(input())
arr = list(map(int,input().split()))
dp = []
#DP
dp.append(arr[0])
for i in range(1, N):
dp.append(dp[-1]+arr[i] if dp[-1]>0 else arr[i])
if len(dp)==1:
print(dp.pop())
else:
print(max(*dp))104ms