[DP] 백준 10211. Maximum Subarray

문제

https://www.acmicpc.net/problem/10211
최대 합을 가진 연속 부분집합 구하기.

주의할 점은, 그냥 합이 큰 부분집합아니고 연속 집합이어야 한다는 점..!

핵심 코드

i 인덱스까지 왔을 때,
끊고 가는게 크냐, 합이 크냐.
dp[i] = max(dp[i-1] + x[i] , x[i])
최종적으로 dp중에 max 찾아주면 가장 큰 부분집합의 합이 들어있는 value를 찾을 수 있다.

참고

원소 합이 가장 컸을 때를 구하기만 하면 되는 거면
dp[i] = max(dp[i-1] + x[i] , dp[i-1])
을 통해 i 인덱스의 값을 합에 포함할 지 아닐지를 판단해주면 된다. 근데 위 문제는 앞에 달린 애들을 버릴거냐 말거냐이다.. 한끝 차이네.

최종 코드

t = int(input())
while t!=0:
    t -= 1
    n = int(input())
    x = list(map(int, input().split()))
    dp = [0]*(n)
    dp[0] = x[0]     
    for i in range(1,n):
        dp[i] = max(dp[i-1] + x[i], x[i])
    print(max(dp))