C++-এ কমপক্ষে k দূরত্বে থাকা এলিমেন্ট দিয়ে সর্বোচ্চ সম সাবসিকোয়েন্স বের করার প্রোগ্রাম

সমস্যা বিবরণ

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

সমাধানের পদ্ধতি (ডাইনামিক প্রোগ্রামিং)

1. MS[i] = ইন্ডেক্স i থেকে শুরু করে সম্ভব সর্বোচ্চ সম।
2. MS[N-1] = arr[N-1]।
3. i = N-2 থেকে 0 পর্যন্ত পিছিয়ে আসুন:
   • যদি i + k + 1 >= N হয় (অর্থাৎ পরবর্তী ভ্যালিড ইন্ডেক্স বাইরে পড়ে), তবে MS[i] = max(arr[i], MS[i+1])।
   • অন্যথায় MS[i] = max(arr[i] + MS[i+k+1], MS[i+1])।
4. MS[0] রিটার্ন করুন।

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

আউটপুট

230

জটিলতা

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