Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में प्रीफिक्स सम का उपयोग करके O(n) में अधिकतम सबएरे सम


समस्या कथन

सकारात्मक और नकारात्मक पूर्णांकों का एक सरणी दिया गया है, उस सरणी में अधिकतम सबएरे सम ज्ञात करें।

उदाहरण

यदि इनपुट सरणी है {-12, -5, 4, -1, -7, 1, 8, -3} तो आउटपुट 9 होगा।

एल्गोरिदम

  • इनपुट सरणी का प्रीफिक्स सम निकालें।

  • प्रारंभ करें: min_prefix_sum = 0, res = -infinite

  • i = 0 से n तक लूप बनाए रखें (n इनपुट सरणी का आकार है)।

    • cand = prefix_sum[i] – min_prefix_sum

    • यदि cand res (अब तक का अधिकतम सबएरे सम) से अधिक है, तो res को cand से अपडेट करें।

    • यदि prefix_sum[i], min_prefix_sum (अब तक का न्यूनतम प्रीफिक्स सम) से कम है, तो min_prefix_sum को prefix_sum[i] से अपडेट करें।

  • res वापस करें।

उदाहरण

#include <bits/stdc++.h> using namespace std; int maximumSumSubarray(int *arr, int n){    int minPrefixSum = 0;    int res = numeric_limits<int>::min();    int prefixSum[n];    prefixSum[0] = arr[0];    for (int i = 1; i < n; i++) {       prefixSum[i] = prefixSum[i - 1] + arr[i];    }    for (int i = 0; i < n; i++) {       res = max(res, prefixSum[i] - minPrefixSum);       minPrefixSum = min(minPrefixSum, prefixSum[i]);    }    return res; } int main(){    int arr[] = {-12, -5, 4, -1, -7, 1, 8, -3};    int n = sizeof(arr) / sizeof(arr[0]);    cout << "Result = " << maximumSumSubarray(arr, n) <<endl;    return 0; }

आउटपुट

जब आप उपरोक्त प्रोग्राम को कंपाइल और निष्पादित करते हैं, तो यह निम्नलिखित आउटपुट उत्पन्न करता है:

Result = 9

  1. - C++ में डिवाइड एंड कंकर का उपयोग करके अधिकतम योग सबएरे

    मान लीजिए हमारे पास धनात्मक और ऋणात्मक मानों के साथ डेटा की एक सूची है। हमें सन्निहित सबएरे का योग ढूंढना है जिसका योग सबसे बड़ा है। मान लीजिए सूची में {-2, -5, 6, -2, -3, 1, 5, -6} है, तो अधिकतम सबएरे का योग 7 है। यह {6, -2, -3, 1, 5} का योग है।हम इस समस्या को डिवाइड एंड कंकर विधि का उपयोग करके हल

  1. - C++ में डिवाइड एंड कन्कर एल्गोरिदम का उपयोग करके अधिकतम सबएरे योग

    मान लीजिए हमारे पास धनात्मक और ऋणात्मक मानों वाले डेटा की एक सूची है। हमें सन्निहित सबएरे का योग ढूंढना है जिसका योग सबसे बड़ा है। मान लीजिए सूची में {-2, -5, 6, -2, -3, 1, 5, -6} है, तो अधिकतम सबएरे का योग 7 है। यह {6, -2, -3, 1, 5} का योग है। हम इस समस्या को डिवाइड एंड कन्कर विधि का उपयोग करके हल

  1. - C++ में बाइनरी सर्च दृष्टिकोण का उपयोग करके अधिकतम सबएरे योग ज्ञात करना

    बाइनरी सर्च एक तेज खोज एल्गोरिदम है जिसकी रन-टाइम जटिलता O(log n) है। यह एल्गोरिदम विभाजन और विजय के सिद्धांत पर काम करता है। इस एल्गोरिदम के ठीक से काम करने के लिए, डेटा संग्रह सॉर्टेड रूप में होना चाहिए। बाइनरी सर्च संग्रह के मध्य तत्व की तुलना करके किसी विशेष आइटम को खोजता है। यदि मेल होता है, त