[BOJ | Python] 10211번: Maximum Subarray

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

 

문제

크기 N인 정수형 배열 X가 있을 때, X의 부분 배열(X의 연속한 일부분) 중 각 원소의 합이 가장 큰 부분 배열을 찾는 Maximum subarray problem(최대 부분배열 문제)은 컴퓨터 과학에서 매우 잘 알려져 있다.

여러분은 N과 배열 X가 주어졌을 때, X의 maximum subarray의 합을 구하자. 즉, max1 ≤ i ≤  j ≤ N (X[i]+...+X[j])를 구하자.

 

입력

입력 파일의 첫 번째 줄에 테스트 케이스의 수를 의미하는 자연수 T가 주어진다. 그 다음에는 T개의 테스트 케이스가 주어진다.

각 테스트케이스 별로 첫 번째 줄에 배열의 크기 N이 주어진다. (1 ≤ N ≤ 1,000)

그리고 두 번째 줄에 배열 X의 내용을 나타내는 N개의 정수가 공백으로 구분되어 주어진다. 이때 주어지는 수는 절댓값이 1,000보다 작은 정수이다.

 

출력

각 테스트케이스 별로 maximum subarray의 합을 줄로 구분하여 출력한다.

 

풀이

for _ in range(int(input())):
    N = int(input())
    X = list(map(int, input().split()))
    prefix = max_sum = X[0]

    for i in range(1, N):
        prefix = max(X[i], prefix + X[i])
        max_sum = max(max_sum, prefix)

    print(max_sum)

 

전형적인 최대 부분합을 구하는 문제이다.

prefix와 max_sum이라는 두가지 변수를 사용하여 구현했다. prefix는 현재의 합 정도로 생각하면 될 것 같다.

만약 prefix가 음수라면, 지금까지의 합 보다 X[i] 하나의 수가 더 클 수 있기 때문에 둘 중 더 큰 수를 prefix 변수에 저장하고, 

기존 최댓값과 현재의 값(prefix) 중 최댓값을 비교해서 더 큰 수를 저장한다.

 

* 처음에 prefix와 max_sum을 0으로 초기화했는데, 이렇게 할 경우 X의 모든 수가 음수라면 문제가 된다!!! 따라서 X의 첫번째 원소로 초기화하도록 변경했다. 항상 경우의수 따져보자 ㅜㅜ