Tổng lớn nhất của hai mảng con không chồng lấn trong C++

Giới thiệu

Cho mảng A và hai độ dài L, M. Tìm tổng lớn nhất của hai mảng con không chồng lấn, một độ dài L, một độ dài M. Hai mảng con có thể theo thứ tự bất kỳ (L trước M hoặc M trước L).

Ví dụ

Đầu vào: A = [0,6,5,2,3,5,1,9,4], L = 1, M = 2 → Đầu ra: 20 (mảng con [9] và [6,5]).

Ý tưởng giải thuật (Tiền tố & Hậu tố)

Tính mảng leftL[i]: tổng lớn nhất của mảng con độ dài L kết thúc tại hoặc trước i.
Tính mảng leftM[i]: tương tự cho độ dài M.
Tính mảng rightL[i]: tổng lớn nhất của mảng con độ dài L bắt đầu tại hoặc sau i.
Tính mảng rightM[i]: tương tự cho độ dài M.
Kết quả = max của:
- leftL[i] + rightM[i+1] (L bên trái, M bên phải)
- leftM[i] + rightL[i+1] (M bên trái, L bên phải)

Ví dụ triển khai (C++)

#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), leftM(n), rightL(n), rightM(n);
        
        // leftL: max sum subarray length L ending at or before i
        int sum = 0;
        for (int i = 0; i < L; i++) sum += A[i];
        leftL[L-1] = sum;
        for (int i = L, j = 0; i < n; i++, j++) {
            sum += A[i] - A[j];
            leftL[i] = max(leftL[i-1], sum);
        }
        
        // leftM
        sum = 0;
        for (int i = 0; i < M; i++) sum += A[i];
        leftM[M-1] = sum;
        for (int i = M, j = 0; i < n; i++, j++) {
            sum += A[i] - A[j];
            leftM[i] = max(leftM[i-1], sum);
        }
        
        // rightL: max sum subarray length L starting at or after i
        sum = 0;
        for (int i = n-1; i > n-1-L; i--) sum += A[i];
        rightL[n-L] = sum;
        for (int i = n-L-1, j = n-1; i >= 0; i--, j--) {
            sum += A[i] - A[j];
            rightL[i] = max(rightL[i+1], sum);
        }
        
        // rightM
        sum = 0;
        for (int i = n-1; i > n-1-M; i--) sum += A[i];
        rightM[n-M] = sum;
        for (int i = n-M-1, j = n-1; i >= 0; i--, j--) {
            sum += A[i] - A[j];
            rightM[i] = max(rightM[i+1], sum);
        }
        
        int ans = 0;
        for (int i = L-1; i <= n-1-M; i++)
            ans = max(ans, leftL[i] + rightM[i+1]);
        for (int i = M-1; i <= n-1-L; i++)
            ans = max(ans, leftM[i] + rightL[i+1]);
        
        return ans;
    }
};

int main() {
    Solution ob;
    vector<int> v = {0,6,5,2,3,5,1,9,4};
    cout << ob.maxSumTwoNoOverlap(v, 1, 2); // 20
    return 0;
}

Đầu vào

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