সর্বোচ্চ সাবসিকোয়েন্স যোগফল যাতে কোনো তিনটি সন্নিহিত নয় (Maximum subsequence sum such that no three are consecutive)

এই টিউটোরিয়ালে আমরা সর্বোচ্চ সাবসিকোয়েন্স যোগফল বের করব যাতে কোনো তিনটি সন্নিহিত পূর্ণসংখ্যা যোগফলে না থাকে।

ধনাত্মক পূর্ণসংখ্যার একটি সিরিজ দেওয়া থাকবে। আমাদের কাজ হল সর্বোচ্চ যোগফল বের করা যাতে কোনো তিনটি সন্নিহিত সংখ্যা যোগফলে অন্তর্ভুক্ত নয়।

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
//returning maximum subsequence without involving
//three consecutive numbers
int maxSumWO3Consec(int arr[], int n) {
    int sum[n];
    if (n >= 1) sum[0] = arr[0];
    if (n >= 2) sum[1] = arr[0] + arr[1];
    if (n > 2) sum[2] = max(sum[1], max(arr[1] + arr[2], arr[0] + arr[2]));
    for (int i = 3; i < n; i++)
        sum[i] = max(max(sum[i - 1], sum[i - 2] + arr[i]), arr[i] + arr[i - 1] + sum[i - 3]);
    return sum[n - 1];
}
int main() {
    int arr[] = { 100, 1000 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << maxSumWO3Consec(arr, n);
    return 0;
}

আউটপুট

1100