C++-এ সর্বোচ্চ যোগফল কঠোরভাবে বর্ধিত সাবাররে খুঁজুন

ধরুন আমাদের 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