C++-এ আডজেসেন্ট উপাদান ছাড়া সর্বোচ্চ যোগফল (O(1) স্পেস)

একটি অ্যারে দেওয়া আছে। কোনো দুটি উপাদান আডজেসেন্ট না হলে সাবসিকোয়েন্সের সর্বোচ্চ যোগফল বের করতে হবে। O(1) এক্সট্রা স্পেস দিয়ে সমাধান।

উদাহরণ

arr[] = {5, 1, 3, 7, 9, 2, 5}

আউটপুট: 22

অ্যালগরিদম

• দুটি ভ্যারিয়েবল: incl (বর্তমান উপাদান অন্তর্ভুক্ত করে যোগফল), excl (বাতিত করে যোগফল)।
• প্রতিটি উপাদানের জন্য: new_excl = max(incl, excl); incl = excl + arr[i]; excl = new_excl;
• শেষে max(incl, excl) রিটার্ন করুন।

C++ প্রোগ্রাম

#include <iostream>
using namespace std;

int findMaxSumWOAdjecent(int arr[], int N) {
    int incl = arr[0];
    int excl = 0;
    for (int i = 1; i < N; i++) {
        int new_excl = max(incl, excl);
        incl = excl + arr[i];
        excl = new_excl;
    }
    return max(incl, excl);
}

int main() {
    int arr[] = {5, 1, 3, 7, 9, 2, 5};
    int N = sizeof(arr)/sizeof(arr[0]);
    cout << "Max sum without adjacent: " << findMaxSumWOAdjecent(arr, N);
    return 0;
}

আউটপুট: Max sum without adjacent: 22