728x90
반응형
문제: https://www.acmicpc.net/problem/1912
풀이
이번 문제는 연속 합의 최댓값을 구하는 문제입니다.
선택을 하냐, 하지 않느냐에 따라 dp[i]가 채워집니다.
어려운 문제는 아니였기 때문에 점화식을 구해서 풀 수 있었습니다.
이전 값(dp[i-1])에 이번 값(arr[i])를 더한 값을 0과 비교해서, 최댓값을 dp[i]에 채우도록 풀었습니다.
n = int(input())
arr = [0] + list(map(int, input().split()))
dp = [0] * (n+1)
if max(arr[1:]) <= 0: # 모두 음수인 경우
ans = max(arr[1:]) # 한개만 더한 값이 max
else:
for i in range(n + 1):
dp[i] = max(dp[i - 1] + arr[i], 0)
ans = max(dp)
print(ans)
728x90
'자료구조 및 알고리즘 > 백준' 카테고리의 다른 글
[python] 1918. 후위 표기식 (0) | 2024.06.12 |
---|---|
[python] 6550. 부분 문자열 ・ try-except 문 (0) | 2024.06.05 |
[python] 2579. 계단 오르기 (1) | 2024.06.05 |
[python] 11726. 2*n 타일링 (2) | 2024.06.04 |
[python] 9095. 1, 2, 3 더하기 (0) | 2024.06.04 |