सब भन्दा ठूलो योग मिल्दो सुबर्रे  


कठिनाई तह सजिलो
बारम्बार सोधिन्छ २ * * ov इनोवेशन ल्याबहरू समग्र अमेजन डे श तथ्य फ्लिपकार्ट हाइड Hasing.com MakeMyTrip MetLife माइक्रोसफ्ट मोर्गन स्टेनले ओला क्याब्स बजेट OYO कोठा PayU Samsung स्नैपडल टेराडाटा भिषा VMware वालमार्ट ल्याबहरू Zoho
एरे डायनामिक प्रोग्रामिंग

समस्या वक्तव्य  

तपाईंलाई पूर्णांकको एक एरे दिइन्छ। समस्या कथन सबैभन्दा ठूलो योग संगत subarray को लागी सोध्न। यसको मतलब सब्ब्रे (निरन्तर तत्वहरू) फेला पार्न बाहेक अरू केहि छैन जुन दिईएको एर्रेमा सबै अन्य सबारीहरू माझमा सब भन्दा ठूलो योग छ।

उदाहरणका  

arr[] = {1, -3, 4, -2, 5, -6, 2}
[2, 4]

स्पष्टीकरण: अनुक्रमणिका २ देखि अनुक्रमणिका to मा सुरू हुने उप-एर्रेमा एर्रे भित्र सब भन्दा ठूलो योग। छ। कुनै पनि अन्य subarray 2 भन्दा सानो राशि दिन्छ।

सब भन्दा ठूलो योग मिल्दो सुबर्रेपिन

 

arr[] = {1, -3, 4, -1, 4, -2, 5, -6, 2}
[2, 6]

स्पष्टीकरण: अनुक्रमणिका २ देखि अनुक्रमणिका to मा सुरू हुने उप-एर्रेमा एर्रे भित्र १० को सब भन्दा ठूलो योग छ।

 

सब भन्दा ठूलो योग संगत सुबर्रे समस्याको लागि एल्गोरिथ्म  

1. Set the maxValue to the minimum value an integer can hold (INT_MIN / Integer.MIN_VALUE) and maxPoint to 0.
2. Set start, end, s to 0.
3. Traverse the array starting from i=0 to i<size(length of the array).
  1. Add the maxPoint and arr[i] and update it into the maxPoint.
  2. Check if maxValue is less than maxPoint, then update the following:
    1. maxValue = maxPoint
    2. start=s
    3. end=i
  3. Check if the maxPoint is less than 0, then update
    1. maxPoint=0
    2. s=i+1
4. Print ‘start’ and ‘end’ as an index and the maxValue as the largest sum.

स्पष्टीकरण

हामीले एउटा दिएका छौं array पूर्णांकको। हामीले सब भन्दा ठूलो योग संगत subarray पत्ता लगाउन सोधेका छौं। यसले नकारात्मक र सकारात्मक पूर्णांकहरू पनि समावेश गर्न सक्दछ। हामीले ती सबै केसहरू सम्हाल्नु पर्छ। यसको लागि हामी एरेलाई केवल एक पटकको लागि ट्र्याभर्स गर्न जाँदैछौं र त्यसैले योसँग जटिलताको समय छ ऊ)। रैखिक समय जटिलतामा हामी अधिकतम मिल्दो सबभर्रे योग फेला पार्नेछौं।

पनि हेर्नुहोस्
एर्रेमा लगातार समय दायरा थप्न अपरेसन

केहि मान सेट अप गर्नुहोस्, जस्तै अधिकतम मूल्य न्यूनतम मानमा एउटा पूर्णांकले समात्न सक्छ, अधिकतम बिन्दु लाई ०, र सुरु, अन्त, र s ०. माथि एरे लाई लम्बाईसम्म ट्र्याभ गर्न सुरु गर्नुहोस् n। योग अधिकतम पोइन्टमा वर्तमान एर्रे एलिमेन्ट थप गर्नुहोस्। यो अधिकतम बिन्दुमा भण्डार गर्नुहोस्, प्रत्येक समय मान i लूपमा वृद्धि, हामी यो अपरेसन गर्छौं। हामीले पहिले नै यसको मूल्य तय गरिसकेका छौं अधिकतम मूल्य एक पूर्णांकको न्यूनतम मानमा हेर्नुहोस् र यदि अधिकभल्यु अधिकतमबिन्दु भन्दा कम छ भने जाँच गर्नुहोस्। यदि यो सत्य हो भने हामी अधिकतम पोइन्टबाट अधिकभल्यूको मान अपडेट गर्न जाँदैछौं, s बाट सुरु गर्नुहोस्। यो सुरु भ्यारीएबलले सुरु हुने उप-एरेको सुरूवातको दायरा सेट अप गर्दछ र हामीसंग अन्त्य हुन्छ, जुन हामी आई (लूप भ्यारीएबल) को साथ अपडेट गर्छौं।

हामी अब जाँच गर्छौं कि छैनौं भने अधिकतम बिन्दु ० भन्दा कम हो, मतलब एरे मानको थप्न अहिले नै नकरात्मक हो। त्यसो भएमा हामी फेरि म्याक्सपोइन्टको मान ० र एस +१ +१ गर्न अपडेट गर्दछौं। यो s सुरूवात दायरा सेट अप गर्न हामीलाई फेरि मद्दत गर्दछ र हामीलाई सब भन्दा ठूलो योग subarray फेला पार्न मद्दत गर्दछ। यो मैक्सवाइन्ट हामी शून्यमा आरम्भ हुनेछौं किनकि हामीले सब भन्दा ठूलो जोड फेला पार्नुपर्नेछ र त्यसपछि हामी सुरु र अन्त्यको मान प्रिन्ट गर्न जानेछौं र सबैभन्दा ठूलो योग सब-एरेको सुरूवात र अन्त्य सूचकको रूपमा। यदि हामीले यो दृष्टिकोण प्रयोग गर्‍यौं भने हामी एकल पासमा सब भन्दा ठूलो योग संगत subarray पाउन सक्छौं।

 

सब भन्दा ठूलो योग समग्र सुबर्रे समस्याको लागि कोड  

C ++ कोड

#include<bits/stdc++.h>
using namespace std;

// This Function prints the Largest Sum Contiguous Subarray
void getLargestSumContiguousSubarray(int arr[], int size)
{
    // initialising variables with starting values
    int maxValue = INT_MIN;
    int  maxPoint = 0;
    int start =0, end = 0, s=0;

    for (int i=0; i< size; i++ )
    {
        maxPoint += arr[i];

        if (maxValue < maxPoint)
        {
            maxValue = maxPoint;
            start = s;
            end = i;
        }

        if (maxPoint < 0)
        {
            maxPoint = 0;
            s = i + 1;
        }
    }
    cout << "Sub-Array starting from "<< start<< " to "<< end<< " has a largest sum of " <<maxValue;
}
int main()
{
    int arr[] = {1, -3, 4, -2, 5, -6, 2};
    int n = sizeof(arr)/sizeof(arr[0]);
    getLargestSumContiguousSubarray(arr, n);
    return 0;
}
Sub-Array starting from 2 to 4 has a largest sum of 7

 

पनि हेर्नुहोस्
चरण Sum Leetcode समाधान द्वारा सकारात्मक चरण प्राप्त गर्न न्यूनतम मूल्य

जावा कोड

class LargestSumSubArray
{
    // This Function prints Largest Sum Contiguous Subarray
    public static void getLargestSumContiguousSubarray(int arr[], int size)
    {
        // initialising variables with starting values
        int maxValue = Integer.MIN_VALUE;
        int  maxPoint = 0;
        int start =0, end = 0, s=0;

        for (int i=0; i< size; i++ )
        {
            maxPoint += arr[i];

            if (maxValue < maxPoint)
            {
                maxValue = maxPoint;
                start = s;
                end = i;
            }

            if (maxPoint < 0)
            {
                maxPoint = 0;
                s = i + 1;
            }
        }
        System.out.println("Sub-Array starting from "+ start + " to "+ end + " has a largest sum of " + maxValue);
    }
    public static void main(String [] args)
    {
        int arr[] = {1, -3, 4, -2, 5, -6, 2};
        int n = arr.length;
        getLargestSumContiguousSubarray(arr, n);
    }
}
Sub-Array starting from 2 to 4 has a largest sum of 7

जटिलता विश्लेषण  

समय जटिलता

किनकि हामी आकार n को इनपुट एर्रेमा एकल लुप चलाइरहेका छौं। यसैले सबै भन्दा ठूलो योगफलको लागि एल्गोरिथ्मको सुसंगत रेखामा समयावधि जटिलता हुन्छ। ऊ) जहाँ "N" एर्रेमा एलिमेन्ट्सको संख्या हो।

ठाउँ जटिलता

हामीले पूर्णांकहरू भण्डारण गर्न एकल 1D इनपुट एरे प्रयोग गरेका छौं। यसैले एक लिनियर अन्तरिक्ष जटिलता योगदान गर्न ठूलो योग समतुल्य सुबर्रे समस्या। ऊ) जहाँ "N" एर्रेमा एलिमेन्ट्सको संख्या हो।