[BOJ/python]10211번 Maximum Subarray

백준 10211번 Maximum Subarray 파이썬

문제 출처 - https://www.acmicpc.net/problem/10211

10211번: Maximum Subarray

쉽고 재밌는 문제다. 흔히들 알고 있는 카데인 알고리즘으로 간단하게 풀 수 있다.

1. 코드

def kadaneSolution():
    N = int(input())
    A = list(map(int,input().split()))
    
   #dp 배열을 따로 만들지 않고 수열에 그대로 덮어 쓰며 진행한다.
    for i in range(1, N):
        A[i]=max(A[i], A[i-1]+A[i]) # 현재 값을 포함한 부분수열 중 최대를 저장한다.
        
    print(max(A))

T = int(input())
for _ in range(T):
		kadaneSolution()

2-1. 구간합 풀이

해당 문제는 구간합으로도 풀 수 있다. 직관적인 풀이는 아니지만 카데인 알고리즘과 마찬가지로 O(N) 시간 안에 풀이가 가능하다.

• 0 - i 구간에서 최대 구간합은 max(prefix[i] - prefix[k]) (0≤k<i) 이다.
• 이 때 prefix[i]는 고정이므로 최대 구간합은 prefix[i] - min(prefix[k]) (0≤k<i)로 표현할 수 있다.
• 0에서 시작하는 구간 합 중 최솟값 즉, min(prefix[k])를 구하는 것이 핵심이다.
• 인덱스가 증가함에 따라 k는 증가한다. prefix[k]의 최솟값은 계속해서 갱신하며 저장한다.

2-2. 구간합 코드

def getMinSolution():
    N = int(input())
    A = list(map(int, input().split()))
    prefix = [0 for _ in range(N)]
    prefix[0]=A[0]
    for i in range(1,N):
        prefix[i]=prefix[i-1]+A[i]
		
		#마찬가지로 dp 테이블을 따로 만들지 않고 진행했다.
    minPrefix = 0
    sol=float('-inf')
    for i in range(N):
        tmp = prefix[i] - minPrefix
        sol = max(tmp, sol)
        minPrefix = min(minPrefix, prefix[i])
        
    print(sol)