सी/सी++ सबसे बड़े सम सन्निहित सबरे के लिए कार्यक्रम?

पूर्णांकों की एक सरणी दी गई है। हमें उन सभी तत्वों का योग ज्ञात करना है जो सन्निहित हैं। जिसका योग सबसे बड़ा है, उसे आउटपुट के रूप में भेजा जाएगा।

गतिशील प्रोग्रामिंग का उपयोग करके हम अधिकतम राशि को वर्तमान अवधि तक संग्रहीत करेंगे। यह सरणी में सन्निहित तत्वों के लिए योग खोजने में मदद करेगा।

Input: An array of integers. {-2, -3, 4, -1, -2, 1, 5, -3}
Output: Maximum Sum of the Subarray is : 7

एल्गोरिदम

मैक्ससम (सरणी, n)

इनपुट - मुख्य सरणी, सरणी का आकार।

आउटपुट - अधिकतम योग।

Begin
   tempMax := array[0]
   currentMax = tempMax
   for i := 1 to n-1, do
      currentMax = maximum of (array[i] and currentMax+array[i])
      tempMax = maximum of (currentMax and tempMax)
   done
   return tempMax
End

उदाहरण

#include<iostream>
using namespace std;
int maxSum( int arr[], int n) {
   int tempMax = arr[0];
   int currentMax = tempMax;
   for (int i = 1; i < n; i++ ) { //find the max value
      currentMax = max(arr[i], currentMax+arr[i]);
      tempMax = max(tempMax, currentMax);
   }
   return tempMax;
}
int main() {
   int arr[] = {-2, -3, 4, -1, -2, 1, 5, -3};
   int n = 8;
   cout << "Maximum Sum of the Sub-array is: "<< maxSum( arr, n );
}

आउटपुट

Maximum Sum of the Sub-array is: 7