[python/파이썬] 백준 10211 Maximum Subarray

알고리즘/python

[python/파이썬] 백준 10211 Maximum Subarray

ㅌㅇㄴ 2022. 7. 11. 20:22

[문제 출처]

https://www.acmicpc.net/problem/10211

10211번: Maximum Subarray

크기 N인 정수형 배열 X가 있을 때, X의 부분 배열(X의 연속한 일부분) 중 각 원소의 합이 가장 큰 부분 배열을 찾는 Maximum subarray problem(최대 부분배열 문제)은 컴퓨터 과학에서 매우 잘 알려져 있

www.acmicpc.net

[문제 풀이]

import sys
input = sys.stdin.readline

T = int(input())

for _ in range(T):
    n = int(input())
    arr = list(map(int, input().split()))
    arr.append(0)

    dp = [0 for _ in range(n)]
    dp[0] = arr[0]

    for i in range(1, n):
        dp[i] = max(dp[i-1]+arr[i], arr[i])

    print(max(dp))