[파이썬 | 알고스팟 | MAXSUM] 최대 연속 부분합 찾기

https://www.algospot.com/judge/problem/read/MAXSUM

algospot.com :: MAXSUM

문제

N개의 정수를 담고 있는 배열 A가 주어졌을 때, 여기서 가능한 연속 부분합을 구하는 프로그램을 작성하라.

여기서 연속 합이라는 것은 배열 A = { a1, a2, ..., aN } 에서 아무 값도 선택을 하지 않거나( 이 경우 합은 0 ), 배열의 임의의 i번째 수 부터 j번째 수 까지( ai, ai+1, ..., aj ) ( 1 <= i <= j <= N )를 합한 값을 뜻한다.

입력

입력의 첫번째 줄에는 테스트 케이스의 개수 T가 입력된다.
그리고 그 다음줄 부터 한줄에 하나씩 T개의 테스트 케이스가 입력된다.
테스트 케이스의 첫번째 줄에는 정수 N(1<=N<=105)가 입력된다.
그리고 그 다음줄에는 N개의 배열에 담긴 숫자가 순서대로 입력된다. 숫자의 범위는 -100이상 100이하의 정수다.

출력

한줄에 하나씩 테스트 케이스의 순서대로 각 테스트케이스에 대한 가장 큰 연속 부분합을 출력한다.

풀이

이 문제에서 요구하는 풀이는 다이나믹 프로그래밍으로 O(N)시간에 해결하는 것이다.

사실 알고리즘 문제해결전략 책에서는 O(NlgN)알고리즘인 분할정복 방식도 충분히 해결가능한 시간제한이라고 하지만, 파이썬의 특성인지 시간초과가 떴다.

 

분할정복 방식을 설명하면, 어떤 arr을 왼쪽과 오른쪽으로 나눠서, 왼쪽에서 최대 연속 부분합과, 오른쪽에서 최대 연속 부분합과, 왼쪽과 오른쪽이 나뉘어지는 경계를 포함하는 최대 연속 부분합의 경계중에서 최대값을 선택하는 방식으로 구성한다.

 

다이나믹 프로그래밍을 설명하면, 어떤 dp[i]는 i번째 까지에서 최대 연속합이 저장되어 있으므로, dp[i+1]은 dp[i]에다가 arr[i+1]을 합쳐서 최대 연속합을 이어나가거나 혹은 arr[i+1]만 뽑아서 처음부터 최대 연속합을 시작하는 방법이 있으므로, 둘 중에 큰 값을 선택하면 된다.

 

	# [파이썬 | 알고스팟 | MAXSUM] 최대 연속 부분합 찾기
	import sys
	read = sys.stdin.readline
	MINVAL = sys.maxsize * -1
	def inefficient(N, arr):
	ret = MINVAL
	for i in range(N):
	for j in range(i, N):
	ret = max(ret, sum(arr[i:j+1]))
	return ret
	def divideAndConquer(N, arr, left, right):
	if left == right:
	return arr[left]
	mid = (left + right) // 2
	leftval, rightval = MINVAL, MINVAL
	lo, hi = mid, mid+1
	while lo>=left:
	leftval = max(leftval, sum(arr[lo:mid+1]))
	lo -= 1
	while hi<=right:
	rightval = max(rightval, sum(arr[mid+1:hi+1]))
	hi += 1
	ret = leftval + rightval
	#print(divideAndConquer(N, arr, left, mid), divideAndConquer(N, arr, mid+1, right), ret)
	return max(divideAndConquer(N, arr, left, mid), divideAndConquer(N, arr, mid+1, right), ret)
	def dynamic(N, arr):
	dp = [0 for _ in range(N)]
	dp[0] = arr[0]
	for i in range(1, N):
	dp[i] = max(dp[i-1] + arr[i], arr[i])
	return max(dp)
	for t in range(int(read())):
	N = int(read())
	arr = list(map(int, read().split()))
	ans = dynamic(N, arr)
	print(ans)

view raw ALGO_MAXSUM.py hosted with ❤ by GitHub