C++로 풀어보는 겹치지 않는 두 부분 배열의 최대 합 구하기

정수 배열 A가 주어졌을 때, 서로 겹치지 않는 두 부분 배열(하위 배열)에 속한 원소들의 합이 최대가 되는 값을 구하는 문제입니다. 이때 두 부분 배열의 길이는 각각 L과 M입니다.

조금 더 정확하게 표현하면, 다음 식을 만족하는 최댓값 V를 찾아야 합니다.

V = (A[i] + A[i+1] + ... + A[i+L-1]) + (A[j] + A[j+1] + ... + A[j+M-1])

단, 아래 두 조건 중 하나를 반드시 만족해야 합니다.

• 0 <= i < i + L - 1 < j < j + M - 1 < 배열 A의 크기
• 0 <= j < j + M - 1 < i < i + L - 1 < 배열 A의 크기

해결 접근 방법

이 문제는 동적 계획법(DP)과 슬라이딩 윈도우 기법을 활용하면 선형 시간 안에 효율적으로 해결할 수 있습니다. 핵심은 각 위치에서 왼쪽 방향과 오른쪽 방향의 최대 부분 배열 합을 미리 계산해 두는 것입니다.

• leftL[i] : 인덱스 0부터 i까지 범위에서 길이 L인 부분 배열의 최대 합
• rightL[i] : 인덱스 i부터 배열 끝까지 범위에서 길이 L인 부분 배열의 최대 합
• leftM[i], rightM[i] : 위와 동일하지만 길이가 M인 경우

L 길이의 부분 배열이 왼쪽에 있고 M 길이의 부분 배열이 오른쪽에 있는 경우와, 그 반대의 경우를 모두 탐색하여 두 합의 최댓값을 구합니다.

알고리즘 단계

1. n을 배열 A의 크기로 설정하고, 크기가 n인 네 개의 배열 leftL, leftM, rightL, rightM을 정의합니다.
2. ret := 0, temp := 0으로 초기화합니다.
3. 처음 L개 원소의 합을 temp에 저장한 뒤, 윈도우를 한 칸씩 오른쪽으로 이동하면서 leftL[i-1]에 현재 윈도우 합(temp)과 이전까지의 최댓값(leftL[i-2]) 중 큰 값을 저장합니다.
4. 같은 방식으로 leftM 배열을 채웁니다.
5. 배열의 오른쪽 끝에서부터 역방향으로 동일한 과정을 반복하여 rightL과 rightM을 채웁니다.
6. 마지막으로 두 가지 배치를 모두 확인합니다.
   • L이 왼쪽, M이 오른쪽 : ret = max(ret, leftL[i] + rightM[i+1])
   • M이 왼쪽, L이 오른쪽 : ret = max(ret, leftM[i] + rightL[i+1])
7. ret을 반환합니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int maxSumTwoNoOverlap(vector<int>& A, int L, int M) {
        int n = A.size();
        vector <int> leftL(n);
        vector <int> leftM(n);
        vector <int> rightL(n);
        vector <int> rightM(n);
        int ret = 0;
        int temp = 0;
        for(int i = 0; i < L; i++){
            temp += A[i];
        }
        for(int i = L, j = 0; i < n; i++, j++){
            leftL[i - 1] = max(temp, i - 2 < 0 ? 0 : leftL[i - 2]);
            temp += A[i];
            temp -= A[j];
        }
        leftL[n - 1] = max(temp, n - 2 < 0 ? 0 : leftL[n - 2]);
        temp = 0;
        for(int i = 0; i < M; i++){
            temp += A[i];
        }
        for(int i = M, j = 0; i < n; i++, j++){
            leftM[i - 1] = max(temp, i - 2 < 0 ? 0 : leftM[i - 2]);
            temp += A[i];
            temp -= A[j];
        }
        leftM[n - 1] = max(temp, n - 2 < 0 ? 0 : leftM[n - 2]);
        temp = 0;
        for(int i = n - 1; i > n - 1 - L; i--){
            temp += A[i];
        }
        for(int i = n - 1 - L, j = n - 1; i >= 0 ; i--, j-- ){
            rightL[i + 1] = max(temp, (i + 2 >= n ? 0 : rightL[i + 2]));
            temp += A[i];
            temp -= A[j];
        }
        rightL[0] = max(temp, rightL[1]);
        temp = 0;
        for(int i = n - 1; i > n - 1 - M; i--){
            temp += A[i];
        }
        for(int i = n - 1 - M, j = n - 1; i >= 0 ; i--, j-- ){
            rightM[i + 1] = max(temp, (i + 2 >= n ? 0 : rightM[i + 2]));
            temp += A[i];
            temp -= A[j];
        }
        rightM[0] = max(temp, rightM[1]);
        for(int i = L - 1; i <= n - 1 - M; i++){
            ret = max(ret, leftL[i] + rightM[i + 1]);
        }
        for(int i = M - 1; i <= n - 1 - L; i++){
            ret = max(ret, leftM[i] + rightL[i + 1]);
        }
        return ret;
    }
};
main(){
    Solution ob;
    vector<int> v1 = {0,6,5,2,3,5,1,9,4};
    cout << (ob.maxSumTwoNoOverlap(v1, 1, 2));
}

입력

[0,6,5,2,3,5,1,9,4]
1
2

출력

20

결과 분석

배열에서 길이 1인 부분 배열 [9]와 겹치지 않는 길이 2인 부분 배열 [6, 5]를 선택하면, 9 + 11 = 20이 되어 최댓값을 얻습니다.

복잡도 분석

• 시간 복잡도 : O(n) — 배열을 앞뒤로 각각 한 번씩 순회합니다.
• 공간 복잡도 : O(n) — 네 개의 보조 배열을 사용합니다.