Tổng lớn nhất của dãy con với các phần tử cách nhau ít nhất k vị trí trong C++

Cho mảng số nguyên và giá trị K. Tìm dãy con có tổng lớn nhất sao cho hai phần tử bất kỳ trong dãy con cách nhau ít nhất K vị trí trong mảng gốc.

Thuật toán (Quy hoạch động)

• Mảng MS[i]: tổng lớn nhất của dãy con hợp lệ bắt đầu từ chỉ số i.
• Duyệt ngược từ N-2 về 0:
  • Nếu i + k + 1 >= N: MS[i] = max(arr[i], MS[i+1]).
  • Ngược lại: MS[i] = max(arr[i] + MS[i+k+1], MS[i+1]).
• Kết quả: MS[0].

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

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

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

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

Đầu ra

230