सख्ती से बढ़ते सब-अर्रे का अधिकतम योग खोजें 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