লাগাতার তিনটি না হলে সর্বোচ্চ সাবসিকোয়েন্স যোগফল (C++ প্রোগ্রাম)

এই সমস্যাতে, আমাদের n সংখ্যক ধনাত্মক পূর্ণসংখ্যা সমন্বিত একটি অ্যারে arr[] দেওয়া আছে। আমাদের কাজ হল এমন সর্বোচ্চ সাবসিকোয়েন্স যোগফল খুঁজে বের করার প্রোগ্রাম তৈরি করা যাতে লাগাতার তিনটি উপাদান নেই।

এখানে, আমাদের অ্যারে থেকে তৈরি সিকোয়েন্সের যোগফল বের করতে হবে যাতে সেখানে লাগাতার তিনটি উপাদান নেই।

অ্যারেতে লাগাতার উপাদান (Consecutive elements): অ্যারেতে সেই উপাদানগুলো যেগুলো একই ক্রমে ইনডেক্স অনুসরণ করে।

arr[0], arr[1], arr[2], …

arr[] = {5, 9, 12, 15}

32

যোগফল = 5 + 12 + 15 = 32

একটি সহজ সমাধান হল একটি অক্সিলিয়ারি অ্যারে তৈরি করা যা বর্তমান ইনডেক্স পর্যন্ত যোগফল সংরক্ষণ করবে। এবং তারপর যোগফল বের করে লাগাতার যোগফল চেক করে ইনডেক্স পর্যন্ত যোগফল বের করা।

প্রথম দুটি যোগফল মানের জন্য:
sumVal[0] = arr[0]
sumVal[1] = arr[0] + arr[1]

তবে তৃতীয় মান সরাসরি বিবেচনা করা যাবে না। এবং যোগফল বিবেচনা করার জন্য, আমরা বর্তমান তিনটি উপাদানের সাথে শর্ত চেক করব। যদি arr[i] বিবেচনা করলে যোগফল বড় হয়, তবে arr[i-1] বা arr[i-2] বাদ দিব। অন্যথায় arr[i] বিবেচনা করব না, যোগফল একই থাকবে।

sum[i] = max(sum[i-3] + arr[i-1] + arr[i], sum[i-2] + arr[i], sum[i-1])

#include 
using namespace std;

int findMaxSubSeqSum(int arr[], int n) {
    int maxSumArr[n];
    maxSumArr[0] = arr[0];
    maxSumArr[1] = arr[0] + arr[1];
    maxSumArr[2] = max(maxSumArr[1], max(arr[1] + arr[2], arr[0] + arr[2]));
    
    for (int i = 3; i < n; i++) {
        int sum1 = maxSumArr[i - 2] + arr[i];
        int sum2 = arr[i] + arr[i - 1] + maxSumArr[i - 3];
        maxSumArr[i] = max(max(maxSumArr[i - 1], sum1), sum2);
    }
    return maxSumArr[n - 1];
}

int main() {
    int arr[] = { 5, 9, 12, 15 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "The maximum subsequence sum such that no three are consecutive is " << findMaxSubSeqSum(arr, n);
    return 0;
}

The maximum subsequence sum such that no three are consecutive is 32