백준 10211번 Maximum Subarray

import sys
sys.stdin = open('input.txt', 'rt')
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 a in range(1, N):
        dp[a] = max(dp[a-1]+arr[a], arr[a])

    print(max(dp))

dp는 항상 아이디어를 떠올리는게 어려운 것 같다.. 사실 그게 dp의 전부긴 하지만..
이 문제 같은 경우에는 dp라는 리스트를 만들어서 누적합을 더해가고 계산할 값이 답겨져 있는 arr리스트의 현재 값과 비교해서 max 값을 넣어주면 되는 문제이다.
부분합이 최대가 되야한다. 계속 값을 더해가면서 현재 값과 비교하면 된다.