[알고리즘][Python] 백준(BOJ) 10211 Maximum Subarray_파이썬

 

10211 Maximum Subarray    www.acmicpc.net/problem/10211

10211번: Maximum Subarray

 

 

문제 풀기 전 공부할 것 : 다이나믹 프로그래밍, 누적 합

 

 

 

 

 

 

 

풀이

<내용>

• 연속하는 부분 배열의 원소의 합이 가장 큰 것을 찾는 문제이다.
• dp를 이용해서 해결할 수 있다.
• 연속하는 부분 배열이기 때문에 이전의 값에서 현재 값을 더한 값(dp[i-1]+arr[i])과 현재 값(arr[i])을 비교해서 더 큰 값을 저장하면 된다.

 

 

<코드>

import sys
input = sys.stdin.readline

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))