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

Cho mảng N số nguyên và giá trị 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 ≥ K (tức là không có hai phần tử nào gần nhau hơn K vị trí).

Thuật toán (DP)

• dp[i]: tổng lớn nhất kết thúc tại i (chứa a[i]).
• Khởi tạo: dp[0]=a[0], dp[i]=max(a[i], dp[i-1]) cho i ≤ k.
• Với i > k: dp[i] = max(a[i], dp[i-(k+1)] + a[i]).
• Kết quả: max của mảng dp.

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

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

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

int main() {
    int arr[] = {6, 7, 1, 3, 8, 2, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 2;
    cout << maxSum(arr, k, n);
    return 0;
}

Đầu ra

15