Maximum sum possible for a sub-sequence such that no two elements appear at a distance < K in the array in C++

ในบทช่วยสอนนี้ เราจะพูดถึงโปรแกรมหาผลรวมสูงสุดที่เป็นไปได้สำหรับลำดับย่อย โดยที่ไม่มีสององค์ประกอบใดๆ อยู่ห่างกันน้อยกว่า K ในอาร์เรย์

เราจะได้รับอาร์เรย์ N จำนวนเต็มและค่า K งานคือหาผลรวมสูงสุดของลำดับย่อยที่รวมองค์ประกอบที่ไม่ใกล้กันกว่า K

ตัวอย่างโค้ด

#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]);
    int max = *max_element(dp, dp + n);
    return max;
}

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;
}

เอาต์พุต

15