Maximum Subarray

문제

크기 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의 합을 줄로 구분하여 출력한다.

예제 입력 1

2
5
1 2 3 4 5
5
2 1 -2 3 -5

예제 출력 1

15
4

코드

import sys

input = sys.stdin.readline

T = int(input())

for i in range(T):
    n = int(input())
    x = list(map(int, input().split()))
    
    result = [x[0]]
    
    for i in range(1, n):
        big = max(result[i-1]+x[i], x[i])
        result.append(big)
    print(max(result))
        

이 최대 부분합 문제는 누적 합을 이용한 문제입니다.

예제 출력 내용을 가져와 보면

배열 : 2 1 -2 3 -5

우선 가장 앞에 있는 값을 먼저 넣는다
R[0] = x[0] = 2
R[1] = max( R[0] + x[1], x[1] ) = max(3, 1) = 3
R[2] = max( R[1] + x[2], x[2] ) = max(1, -2) = 1
R[3] = max( R[2] + x[3], x[3] ) = max(4, 3) = 4
R[4] = max( R[3] + x[4], x[4] ) = max(-1, -5) = -1

=> R[2, 3, -1, 4, -1]

최대 부분합 문제에선 카데인 알고리즘을 많이 사용하는 것 같습니다.
참고 : https://juneyr.dev/2019-11-21/maximum-subarray