[leetcode] 689. Maximum Sum of 3 Non-Overlapping Subarrays

https://leetcode.com/problems/maximum-sum-of-3-non-overlapping-subarrays/description/

 

해당 문제는 정수배열 nums 와 k 가 주어졌을 때 겹치지 않는 최대합을 가지는 길이 k 의 부분 배열 3개를 찾아서 반환하는 문제입니다

여기서 주의할 점은 정답이 여러개 인 경우 index 가 작은것 부터 반환해야 합니다.

 

Approach

해당 문제는 총 3개의 부분 배열을 반환해야 합니다 그러므로 3 개의 section 으로 분할 할 수 있고 이것을 left, middle, right 라고 정의 하겠습니다.

 

먼저 sliding window 를 통해 구간 합을 미리 구해 두겠습니다.

val sums = IntArray(n) { i ->
    nums.slice(i until i + k).sum()
}

 

그런 다음 왼쪽에서 시작했을때의 최대값을 계산합니다.

val left = IntArray(n)
var maxIndex = 0
for (i in 0 until n) {
    if (sums[i] > sums[maxIndex]) {
        maxIndex = i
    }
    left[i] = maxIndex
}

 

 

마찬 가지로 오른쪽에서 시작했을때의 최대값을 계산합니다.

val right = IntArray(n)
maxIndex = n - 1
for (i in n - 1 downTo 0) {
    if (sums[i] >= sums[maxIndex]) {
        maxIndex = i
    }
    right[i] = maxIndex
}

 

 

마지막으로 합이 가장 큰 최적의 조합을 찾습니다.

for (i in k until n - k) {
    val leftIndex = left[i - k]
    val rightIndex = right[i + k]
    val totalSum = sums[leftIndex] + sums[i] + sums[rightIndex]
    
    if (totalSum > maxSum) {
        maxSum = totalSum
        result[0] = leftIndex
        result[1] = i
        result[2] = rightIndex
    }
}

 

 

• 시간 복잡도: O(n)
  • 구간합 계산: O(n)
  • 왼쪽/오른쪽 최대값 계산: 각각 O(n)
  • 최적 조합 찾기: O(n)
• 공간 복잡도: O(n)
  • sums, left, right 배열: 각각 O(n)

 

전체 코드

class Solution {
    fun maxSumOfThreeSubarrays(nums: IntArray, k: Int): IntArray {
        val n = nums.size - k + 1

        val sums = IntArray(n) { i ->
            nums.slice(i until i + k).sum()
        }

        val left = IntArray(n)
        var maxIndex = 0

        for (i in sums.indices) {
            if (sums[i] > sums[maxIndex]) {
                maxIndex = i
            }
            left[i] = maxIndex
        }

        val right = IntArray(n)
        maxIndex = n - 1

        for (i in n - 1 downTo 0) {
            if (sums[i] >= sums[maxIndex]) {
                maxIndex = i
            }
            right[i] = maxIndex
        }

        val result = IntArray(3)
        var maxSum = Int.MIN_VALUE

        for (i in k until sums.size - k) {
            val leftIdx = left[i - k]
            val rightIdx = right[i + k]
            val sum = sums[leftIdx] + sums[i] + sums[rightIdx]
            if (sum > maxSum) {
                maxSum = sum
                result[0] = leftIdx
                result[1] = i
                result[2] = rightIdx
            }
        }

        return result
    }
}