728x90
반응형
10211번: Maximum Subarray
크기 N인 정수형 배열 X가 있을 때, X의 부분 배열(X의 연속한 일부분) 중 각 원소의 합이 가장 큰 부분 배열을 찾는 Maximum subarray problem(최대 부분배열 문제)은 컴퓨터 과학에서 매우 잘 알려져 있
www.acmicpc.net
t = int(input())
def max_sub():
n = int(input())
data = list(map(int,input().split()))
for i in range(1,len(data)):
data[i] += data[i-1] if data[i-1]>0 else 0
return max(data)
p = []
for i in range(t):
p.append(max_sub())
for i in range(t):
print(p[i])728x90
반응형
'백준 > 다이나믹 프로그래밍' 카테고리의 다른 글
| # 10942 팰린드롬? 파이썬 (0) | 2021.04.09 |
|---|---|
| # 1890 점프 파이썬 (0) | 2021.04.08 |
| # 9465 스티커 파이썬 (0) | 2021.03.11 |
| # 11722 가장 긴 감소하는 부분 수열 (0) | 2020.09.17 |
| # 1965 상자넣기 (0) | 2020.09.17 |