[백준] Maximum Subarray - 10211번 문제 (Python)

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

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

코드 정답

import sys
input = sys.stdin.readline

# 10211
t = int(input())

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

풀이

1~2행 : input 보다 빠른 sys.stdin.readline 을 사용하기 위하여 작성한 문장입니다.

import sys
input = sys.stdin.readline

5행 : 정수값 하나를 입력받아 변수 t에 저장합니다. t는 입력받는 것을 반복할 횟수입니다.

t = int(input())

7~14행 : t번 만큼 8~13행을 반복합니다. 정수값 하나를 입력받아 변수 n에 저장합니다. 다음 행에서는 띄워쓰기를 기준으로 정수값을 입력받아 리스트 형태로 변수 li에 저장합니다.

인덱스 값이 0으로 이루어져 있으며 n 개의 인덱스를 가진 변수 dp를 선언해주고 dp[0] 에 li[0]이 저장되어 있는 값을 넣어줍니다. 이후 n-1번 13행을 반복하며 dp[i]에 알맞은 값을 저장해줍니다. max() 안에서는 dp[i-1]+li[i] 의 값과 li[i] 의 값 중에서 더욱 큰 값을 dp[i]에 저장하게 됩니다. 12행의 반복문에서 빠져나오게 된다면 dp에 저장되어 있는 가장 큰 값을 출력합니다.

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