MaxDoubleSliceSum

🔗 문제 링크

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

❔ 문제 설명

A non-empty array A consisting of N integers is given.

A triplet (X, Y, Z), such that 0 ≤ X < Y < Z < N, is called a double slice.

The sum of double slice (X, Y, Z) is the total of A[X + 1] + A[X + 2] + ... + A[Y − 1] + A[Y + 1] + A[Y + 2] + ... + A[Z − 1].

For example, array A such that:

A[0] = 3
A[1] = 2
A[2] = 6
A[3] = -1
A[4] = 4
A[5] = 5
A[6] = -1
A[7] = 2

contains the following example double slices:

double slice (0, 3, 6), sum is 2 + 6 + 4 + 5 = 17,
double slice (0, 3, 7), sum is 2 + 6 + 4 + 5 − 1 = 16,
double slice (3, 4, 5), sum is 0.
The goal is to find the maximal sum of any double slice.

Write a function:

def solution(A)

that, given a non-empty array A consisting of N integers, returns the maximal sum of any double slice.

For example, given:

A[0] = 3
A[1] = 2
A[2] = 6
A[3] = -1
A[4] = 4
A[5] = 5
A[6] = -1
A[7] = 2

the function should return 17, because no double slice of array A has a sum of greater than 17.

⚠️ 제한사항

• 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].

---

💡 풀이 (언어 : Python)

어려운 문제였다. 타인의 풀이를 보고 다시 작성해 보았다. 풀이의 아이디어는 Y를 기준으로 왼쪽 수들의 합, 오른쪽 수들의 합을 나눠서 계산한 두개의 배열을 만들고 다시 Y를 기준으로 왼쪽, 오른쪽 합들의 합의 최대값을 구하는 것이다. 이 아이디어를 보면서 이해하는데도 시간이 좀 걸렸다. 그리고 전부 음수인 케이스는 안될것 같은데? 했지만 조건에서 X, Y, Z를 0이상으로 규정했다. 다음부터는 꼼꼼히 읽자. 시간복잡도는 $O(N)$

def solution(A):
    length = len(A)
    leftSum = [0 for i in range(length)]
    rightSum = [0 for i in range(length)]
    maximum = 0

    for i in range(1, length-1):
        leftSum[i] = max(0, leftSum[i-1] + A[i])
    
    for i in range(length-2, 0, -1):
        rightSum[i] = max(0, rightSum[i+1] + A[i])

    for i in range(1, length-1):
        maximum = max(maximum, leftSum[i-1] + rightSum[i+1])
    
    return maximum