Tổng lớn nhất dãy con với khoảng cách giữa các phần tử ≥ K trong C++

Mô tả bài toán

Cho mảng arr[] và số k. Tìm tổng lớn nhất của dãy con sao cho khoảng cách giữa hai phần tử bất kỳ trong dãy con là ≥ k (chỉ số khác nhau ≥ k+1).

Ví dụ: arr = {6,2,5,1,9,11,4}, k=2 → 16 (chọn 5 và 11).

Giải thuật (Quy hoạch động)

1. dp[i] = tổng lớn nhất dãy con kết thúc tại i (hoặc bắt đầu từ i tùy định nghĩa).
2. Khởi tạo dp[0] = arr[0].
3. Với i từ 1 đến n-1:
   • Nếu i < k: dp[i] = max(arr[i], dp[i-1]).
   • Ngược lại: dp[i] = max(arr[i], dp[i-(k+1)] + arr[i]).
4. Kết quả = max(dp[i]).

Ví dụ minh họa (C++)

#include <iostream>
using namespace std;

int calcMaxSumSubSeq(int arr[], int k, int n) {
    vector dp(n);
    int maxSum = -1;
    dp[0] = arr[0];
    for (int i = 1; i < n; i++) {
        if (i < k) dp[i] = max(arr[i], dp[i-1]);
        else dp[i] = max(arr[i], dp[i-(k+1)] + arr[i]);
    }
    for (int i = 0; i < n; i++) maxSum = max(maxSum, dp[i]);
    return maxSum;
}

int main() {
    int arr[] = {6,2,5,1,9,11,4};
    int n = 7, k = 2;
    cout << "Maximum sum: " << calcMaxSumSubSeq(arr, k, n);
    return 0;
}

Đầu ra

Maximum sum: 16