[실버 4] 백준 10211 - Maximun Subarray (파이썬)

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

풀이

• 여러 테스트 케이스가 주어진다.
• 각 케스트 케이스마다, 연속된 구간의 합 중 최대값을 구하는 문제

누적합 배열 psum을 생성한다.

psum = [0] * N
psum[0] = X[0]

• psum[i] = X[0] + X[1] + … + X[i]

for i in range(1, N) :
  psum[i] = psum[i - 1] + X[i]

• 구간 합을 빠르게 계산하려고 누적합 배열을 사용한다.

for i in range(N) :
  for j in range(i, N) :
      range_sum = psum[j]
      if i > 0 :
          range_sum -= psum[i - 1]

      if max_sum < range_sum :
          max_sum = range_sum

• 모든 구간을 탐색하며, (i, j) 구간의 합은 psum[j] - psum[i - 1]
• 각 구간 합을 구하면서 최대값을 갱신한다.
• 최종적으로 최대 구간 합을 출력한다.

시간 복잡도 분석

• 구간 (i, j)를 모두 탐색 → O(N^2)
• 누적합을 만들 때 O(N)
• 총 O(N^2)라서, N이 크면 느릴수 있다.

코드

# 백준 10211 - Maximum Subarray
# 분류 : 누적합

T = int(input())
for _ in range(T) :
    N = int(input())
    X = list(map(int, input().split()))

    psum = [0] * N
    psum[0] = X[0]
    for i in range(1, N) :
        psum[i] = psum[i - 1] + X[i]

    max_sum = -1e9
    for i in range(N) :
        for j in range(i, N) :
            range_sum = psum[j]
            if i > 0 :
                range_sum -= psum[i - 1]

            if max_sum < range_sum :
                max_sum = range_sum
    
    print(max_sum)

• DP 코드

# 백준 10211 - Maximum Subarray
# 분류 : 다이나믹 프로그래밍

T = int(input())

for _ in range(T) :
    N = int(input())
    A = list(map(int, input().split()))

    D = [0] * N
    D[0] = A[0]
    for i in range(1, N) :
        D[i] = max(A[i], A[i] + D[i - 1])
    
    print(max(D))