सबसे बड़ा योग सन्निहित सबरे

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

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

इनपुट और आउटपुट

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

एल्गोरिदम

maxSum(array, 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