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