Dãy con tổng lớn nhất với các phần tử cách nhau ít nhất k vị trí 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 hai phần tử bất kỳ trong dãy con có chỉ số khác nhau ít nhất k+1 (tức là cách nhau ≥ k phần tử).

Ví dụ: arr = {2,3,7,9,2,8,3}, k=2 → 15 (chọn 7 và 8).

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

1. dp[i] = tổng lớn nhất từ i đến n-1.
2. dp[n-1] = arr[n-1].
3. Với i từ n-2 xuống 0:
   • Nếu i+k+1 ≥ n: dp[i] = max(arr[i], dp[i+1]).
   • Ngược lại: dp[i] = max(arr[i] + dp[i+k+1], dp[i+1]).
4. Kết quả dp[0].

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

#include <bits/stdc++.h>
using namespace std;

int calcMaxSubSeqSum(int arr[], int N, int k) {
    vector dp(N);
    dp[N-1] = arr[N-1];
    for (int i = N-2; i >= 0; i--) {
        if (i + k + 1 >= N) dp[i] = max(arr[i], dp[i+1]);
        else dp[i] = max(arr[i] + dp[i+k+1], dp[i+1]);
    }
    return dp[0];
}

int main() {
    int N = 10, k = 2;
    int arr[] = {50,70,40,50,90,70,60,40,70,50};
    cout << "Maximum sum: " << calcMaxSubSeqSum(arr, N, k);
    return 0;
}

Đầu ra

Maximum sum: 230