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

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

10211번: Maximum Subarray

Problem

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

조건

• 입력 파일의 첫 번째 줄에 테스트 케이스의 수를 의미하는 자연수 T가 주어진다. 그 다음에는 T개의 테스트 케이스가 주어진다.
• 각 테스트케이스 별로 첫 번째 줄에 배열의 크기 N이 주어진다. (1 ≤ N ≤ 1,000)
• 그리고 두 번째 줄에 배열 X의 내용을 나타내는 N개의 정수가 공백으로 구분되어 주어진다. 이때 주어지는 수는 절댓값이 1,000보다 작은 정수이다.

SOL

Maximum subarray problem(최대 부분배열 문제)을 안다면, 쉽게 풀리는 문제이다.

모른다고 하더라도, 누적합을 구하고, 시작점을 어떻게 바꿔줄지에 대해서 고민을 한다면, 충분히 풀 수 있을거 같다!!

LIS에 대해서 고민을 많이해서 그런지 몰라도, 사실 위의 개념을 모른체로 구현을 했더니 ,맞아서 놀랐던 문제!

import sys
input = sys.stdin.readline

tc= int(input())

while tc:
    N = int(input())
    seq=list(map(int,input().split()))
    DP=[0]*N
    DP[0] = seq[0]
    
    for i in range(1,N):
        DP[i] = max(DP[i-1]+seq[i],seq[i])
    print(max(DP))
    tc-=1