Leetcode 689. Maximum Sum of 3 Non-Overlapping Subarrays 풀이

문제

Given an integer array nums and an integer k, 
find three non-overlapping subarrays of length k with maximum sum and return them.

Return the result as a list of indices representing the starting position of each interval (0-indexed). 
If there are multiple answers, return the lexicographically smallest one.

• 정수 배열과 정수 k가 주어진다.
• nums에서 k개 사이즈의 배열 세개를 고른다고 가정한다.
• 이 배열들이 겹치지 않으면서 전체 합이 가장 커야 한다고 가정한다.
• 리턴 값은 세 배열의 시작값들로 구성하되, 여러 경우가 있을시 사전순으로 앞인 값을 리턴한다.
  • Ex. [0, 3, 5] 와 [1, 3, 5] 중 [0, 3, 5] 리턴

예시

nums = [1,2,1,2,6,7,5,1], k = 2

• [0, 3, 5] (1, 2), (2, 6), (7, 5) 와
• [1, 3, 5] (2, 1), (2, 6), (7, 5) 등이 가능한데
• 가장 사전순으로 빠른 [0, 3, 5] 가 답이 된다.

제한

• $1 <= nums.length <= 2 * 10^4$
• $1 <= nums[i] < 2^{16}$
• $1 <= k <= floor(nums.length / 3)$

풀이

• 순서에 따라 수행하고 DP를 한 뒤 정답은 트래킹해낸다.

1. prefix sum을 이용해서 k 사이즈의 부분배열들의 합을 먼저 구한다.

2. 2차원 DP를 이용해 col index의 값이 1, 2, 3 번째에 각각 선택될때 ( 시작값으로 ) 최댓값을 트래킹

3. 3번째 선택된 값들 중에 가장 큰 값을 기준으로 가장 먼저 등장한 값을 위주로 앞에 선택된 값을 트래킹

예시로 [1,2,1,2,6,7,5,1] 과 2를 들어보겠다.

1번 수행

        partial = [0]
		
        # Prefix sum 수행
        for num in nums:
            partial.append(partial[-1] + num)

        ksum = []

		# Prefix sum을 이용해 k 사이즈의 배열의 합을 구함
        for i in range(len(nums) - k + 1):
            ksum.append(partial[i + k] - partial[i])

        N = len(ksum)

결과

[3, 3, 3, 8, 13, 12, 6]

2번 수행

# 값을 저장할 dp
dp = [[0] * N for _ in range(3)]

		# 첫번째 선택은 아무거나 가능
        for i in range(len(ksum)):
            dp[0][i] = ksum[i]

		# 2, 3번째 선택
        for i in range(1, 3):
            maxima = 0
            for j in range(i * k, len(ksum)):
                maxima = max(dp[i-1][j-k], maxima)
                dp[i][j] = maxima + ksum[j]

결과 ( dp )

[3, 3, 3, 8, 13, 12, 6]
[0, 0, 6, 11, 16, 20, 19]
[0, 0, 0, 0, 19, 23, 22]

3번 수행

ans = [0, 0, 0]

        third_max = max(dp[2])
        third_point = dp[2].index(third_max)

        ans[2] = third_point

        second_point = dp[1].index(third_max - ksum[third_point])

        ans[1] = second_point

        first_point = dp[0].index(dp[1][second_point] - ksum[second_point])

        ans[0] = first_point

        return ans

• 값 도출됨.

생각

• 1차원 배열로도 충분히 가능할듯