C++-এ অ্যারেতে দূরত্ব < K না হয় এমন সাবসিকোয়েন্স-এর সর্বোচ্চ সম বের করার প্রোগ্রাম

সমস্যা বিবরণ

একটি অ্যারে এবং মান K দেওয়া থাকলে, এমন সাবসিকোয়েন্স খুঁজে বের করতে হবে যাতে যেকোনো দুই এলিমেন্টের দূরত্ব K-এর চেয়ে কম নয়, এবং সম সর্বোচ্চ হয়।

সমাধানের পদ্ধতি (DP)

1. বেস কেস: n=0 → 0, n=1 → arr[0], n=2 → max(arr[0],arr[1])।
2. dp[i] = ইন্ডেক্স i পর্যন্ত সর্বোচ্চ সম।
3. dp[0] = arr[0]।
4. i = 1 থেকে k: dp[i] = max(arr[i], dp[i-1])।
5. i = k+1 থেকে n-1: dp[i] = max(arr[i], dp[i-(k+1)] + arr[i])।
6. dp অ্যারেতে সর্বোচ্চ মান রিটার্ন করুন।

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]);
    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

জটিলতা

• সময়: O(n)
• স্থান: O(n)