[Python/파이썬] 백준 10211번 Maximum Subarray

10211번: Maximum Subarray

 

코드

for _ in range(int(input())):
    n = int(input())
    x = list(map(int, input().split()))
    # 누적합
    preSum = [0]
    for i in range(n):
        preSum.append(preSum[-1]+x[i])
    # 브루트포스
    ans = -int(1e9)
    for l in range(n):
        for r in range(l+1, n+1):
            if preSum[r]-preSum[l] > ans:
                ans = preSum[r]-preSum[l]
    print(ans)

 

1. 배열 X의 누적합 preSum을 구한다.

2. 이 누적합을 이용하여 X의 원소들의 부분 배열 중 합이 가장 큰 값을 구하면 된다. 부분 배열의 합은 만약 x[a]에서 x[b]까지의 합을 구한다면 preSum[b+1]-preSum[a]이다. (preSum의 0번 요소는 0이므로 b에 1을 더하면 되는 것)