Lesson9. Maximum slice problem - MaxDoubleSliceSum

MaxDoubleSliceSum - Find the maximal sum of any double slice.

https://app.codility.com/programmers/lessons/9-maximum_slice_problem/max_double_slice_sum/

문제요약

N개의 정수 배열 A가 있고, triplet (X, Y, Z) 0<=X<Y<Z<N은 double slice로 불린다. double slice의 합은 A[X+1] + A[X+2] + ... + A[Y-1] + A[Y+1] + A[Y+2] + ... + A[Z-1]이다. A의 double slice 중 최대 합을 찾아라.

Assume that:

N is an integer within the range [3..100,000];

each element of array A is an integer within the range [−10,000..10,000].

Complexity:

expected worst-case time complexity is O(N);

expected worst-case space complexity is O(N) (not counting the storage required for input arguments).

풀이

Y를 기준으로 왼쪽과 오른쪽 부분의 합의 최대값을 구한 후 그 두 합이 다시 최대가 되는 값을 찾는다.

즉 왼쪽합 [i]는 i를 포함한 왼쪽의 값들의 합이고 오른쪽합 [i]는 i를 포함한 오른쪽 값들의 합이다. 단, X와 Y 또는 Y와 X를 인접하게 선택하면 각 부분합은 0이되므로 각 부분합은 0보다 작을 수 없다. 각각 구한 후 1부터 N-2까지 반복하면서 각각 왼쪽합[i-1] + 오른쪽합[i+1]의 최대값을 찾는다.

	def solution(A):
	leftMaxSum = [0] * len(A)
	rightMaxSum = [0] * len(A)
	for i in range(1,len(A)-1):
	leftMaxSum[i] = max(0, leftMaxSum[i-1] + A[i])
	for i in range(len(A)-2, 0, -1):
	rightMaxSum[i] = max(0, rightMaxSum[i+1] + A[i])
	maxSum = 0
	for i in range(1, len(A)-1):
	maxSum = max(maxSum, rightMaxSum[i+1] + leftMaxSum[i-1])
	return maxSum

view raw 9_1_MaxDoubleSliceSum.py hosted with ❤ by GitHub