[Python] leetcode-1031. Maximum Sum of Two Non-Overlapping Subarrays

Given an integer array nums and two integers firstLen and secondLen, return the maximum sum of elements in two non-overlapping subarrays with lengths firstLen and secondLen.
The array with length firstLen could occur before or after the array with length secondLen, but they have to be non-overlapping.
A subarray is a contiguous part of an array.

길이가 firstlen 인 연속 구간 하나와 길이가 길이가 secondLen 인 연속 구간 하나를 고르되, 두 구간이 겹치면 안된다. 이 때 두 구간의 모든 원소의 합산의 최댓값을 구하는 문제이다! (단, first와 second 간의 순서는 상관없음)

처음에는 각 길이에서 최댓값인 구간을 각각 고르면 되겠지?라고 생각했지만, 이렇게 고른 두 구간이 서로 겹칠 수 있고, 설령 겹치지 않더라도 전역 최적을 보장하지 않는 반례가 있어서 포기했다.
또, 큰 합을 가진 구간부터 먼저 고르고 나머지를 고르는 그리디도 반례가 존재했다. (큰 구간을 먼저 고르면 다른 구간의 선택지가 급격히 줄어 전역 최적을 놓칠 수 있음)

그래서 접근을 바꿔, 경계(분할점)를 기준으로 생각했다. 즉,

왼쪽에 길이 firstLen 구간, 오른쪽에 길이 secondLen 구간이 오도록 하고(겹치지 않게),

반대로 왼쪽에 secondLen, 오른쪽에 firstLen이 오도록 하는 경우도 모두 살펴서,
두 경우 중 더 큰 값을 답으로 취한다.

구현은 슬라이딩 윈도우+prefix 최댓값 유지로 O(n)에 할 수 있다:

1. max_sum(L, M) (L-구간이 앞, M-구간이 뒤)

• 오른쪽으로 진행하면서 길이 L 윈도우의 최댓합 maxL을 갱신한다.
• 동시에 그 뒤에 오는 길이 M 윈도우 합과 더해 maxL+Msum의 최댓값을 유지한다.

2. 최종 답 = max(max_sum(firstLen, secondLen), max_sum(secondLen, firstLen))

이 방식은 매 순간 “왼쪽에서 끝나는 L-구간의 최댓값”을 불변식으로 유지하며, 그 바로 뒤에 붙는 M-구간 합과 결합하므로 겹침을 원천 차단하면서 전역 최적을 탐색한다.

🐋정답 코드🐋

class Solution(object):
    def maxSumTwoNoOverlap(self, nums, firstLen, secondLen):
        """
        :type nums: List[int]
        :type firstLen: int
        :type secondLen: int
        :rtype: int
        """
        def max_sum(L,M):
            n=len(nums)
            Lsum=sum(nums[:L]) # 길이가 L인 구간의 합
            Msum=sum(nums[L:L+M]) # 그 바로 뒤에 붙는 길이 M인 구간의 합
            res=Lsum+Msum   # 지금까지 찾은 최대 합
            maxL=Lsum   # 현재 분할점 기준, 왼쪽에서 끝나는 길이 L 구간의 최대 합
            for i in range(L+M,n):
                Msum+=nums[i]-nums[i-M] # 새로 들어온 오른쪽 값 nums[i] 더하고 왼쪽에서 빠진 값 nums[i-M] 뺌
                Lsum+=nums[i-M]-nums[i-M-L] # L의 새 오른쪽 끝이 i-M이 되므로 nums[i-M]가 들어오고, L의 왼쪽에서 빠지는 값은 nums[i-M-L].
                maxL=max(maxL,Lsum) # 왼쪽 L-구간 최대합 갱신
                res=max(res,maxL+Msum)  # 현재 M-구간(오른쪽)과, 그 앞쪽 어디까지든 나올 수 있었던 최고 L-구간을 합쳐서 전역 최댓값 갱신.
            return res
        return max(max_sum(firstLen,secondLen),max_sum(secondLen,firstLen))