মনে করুন আমাদের n পূর্ণসংখ্যার একটি অ্যারে আছে। স্ট্রিক্টলি ইনক্রিজিং সাব-অ্যারেগুলোর সর্বোচ্চ যোগফল বের করতে হবে। তাই যদি অ্যারেটি হয় [1, 2, 3, 2, 5, 1, 7], তবে যোগফল হবে 8। এই অ্যারেতে তিনটি স্ট্রিক্টলি ইনক্রিজিং সাব-অ্যারে আছে: {1, 2, 3}, {2, 5} এবং {1, 7}। সর্বোচ্চ যোগফলযুক্ত সাব-অ্যারে হল {1, 7}
এই সমস্যাটি সমাধানের জন্য, আমাদের সর্বোচ্চ যোগফল এবং বর্তমান যোগফল ট্র্যাক রাখতে হবে। প্রতিটি উপাদান arr[i] এর জন্য যদি এটি arr[i-1]-এর চেয়ে বড় হয়, তবে এটি বর্তমান যোগফলে যোগ করুন, অন্যথায় arr[i] আরেকটি সাব-অ্যারের শুরুর বিন্দু। তাই আমরা বর্তমান যোগফলকে অ্যারে হিসেবে আপডেট করব। বর্তমান যোগফল আপডেট করার আগে, প্রয়োজনে সর্বোচ্চ যোগফল আপডেট করব।
উদাহরণ
#include <iostream>
using namespace std;
int maximum(int a, int b) {
return (a > b) ? a : b;
}
int maximum_sum_incr_subarr(int array[], int n) {
int max_sum = 0;
int current_sum = array[0];
for (int i = 1; i < n; i++) {
if (array[i - 1] < array[i])
current_sum = current_sum + array[i];
else {
max_sum = maximum(max_sum, current_sum);
current_sum = array[i];
}
}
return max(max_sum, current_sum);
}
int main() {
int arr[] = {1, 2, 3, 2, 5, 1, 7};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Maximum sum: " << maximum_sum_incr_subarr(arr, n);
}
আউটপুট
Maximum sum: 8
