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

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

डायनामिक प्रोग्रामिंग का उपयोग करके हम वर्तमान टर्म तक के अधिकतम योग को स्टोर करेंगे। यह ऐरे में सन्निहित तत्वों के योग को ढूंढने में मदद करेगा।

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

इनपुट: पूर्णांकों का एक ऐरे
{-2, -3, 4, -1, -2, 1, 5, -3}

आउटपुट: सबऐरे का अधिकतम योग है: 7

एल्गोरिदम

maxSum(array, n)

इनपुट: मुख्य ऐरे, ऐरे का आकार
आउटपुट: अधिकतम योग

शुरुआत
    tempMax := array[0]
    currentMax = tempMax
    i := 1 से n-1 तक, करें
        currentMax = array[i] और (currentMax + array[i]) का अधिकतम
        tempMax = currentMax और tempMax का अधिकतम
    पूर्ण
    वापस tempMax
अंत

उदाहरण (C++ कोड)

#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++) {
        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