홍우진의 개발 일기장
[백준] 10211번: Maximum Subarray/ 파이썬 본문
728x90
반응형
문제 링크
https://www.acmicpc.net/problem/10211
10211번: Maximum Subarray
크기 N인 정수형 배열 X가 있을 때, X의 부분 배열(X의 연속한 일부분) 중 각 원소의 합이 가장 큰 부분 배열을 찾는 Maximum subarray problem(최대 부분배열 문제)은 컴퓨터 과학에서 매우 잘 알려져 있
www.acmicpc.net
풀이 코드
t = int(input())
for _ in range(t):
n = int(input())
arr = list(map(int, input().split()))
dp = [0] * n
dp[0] = arr[0]
for i in range(1, n):
dp[i] = max(dp[i-1]+arr[i], arr[i])
print(max(dp))코드 해석
이전의 값에서 현재 값을 더한 값과 현재 값을 비교하여
더 큰값을 리스트에 계속 저장한다.
728x90
반응형
'알고리즘 > 백준' 카테고리의 다른 글
| [백준] 1205번: 등수 구하기/ 파이썬 (0) | 2022.08.31 |
|---|---|
| [백준] 1755번: 숫자놀이/ 파이썬 (0) | 2022.08.30 |
| [백준] 5568번: 카드 놓기/ 파이썬 (0) | 2022.08.29 |
| [백준] 2828번: 사과 담기 게임/ 파이썬 (0) | 2022.08.27 |
| [백준] 16435번: 스네이크버드/ 파이썬 (0) | 2022.08.26 |
Comments