अधिकतम सुबर्रे लीटकोड समाधान


कठिनाई तह सजिलो
बारम्बार सोधिन्छ एडोब अमेजन एप्पल ब्लूमबर्ग बाइटडेन्स सिस्को फेसबुक Goldman सैक्स गुगल जेपी मर्गन LinkedIn माइक्रोसफ्ट बजेट PayPal पेटम Uber
एरे विभाजित र विजय गर्नुहोस् डायनामिक प्रोग्रामिंग

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

एक पूर्णाray्क एरे नम्बरहरू दिइयो, संगत फेला पार्नुहोस् सुबर्रे (कम्तिमा एक संख्या समावेश गरीएको) जससँग सब भन्दा ठूलो योग छ र त्यसको योग फर्काउँछ।

उदाहरणका

nums = [-2,1,-3,4,-1,2,1,-5,4]
6

व्याख्या:

[,, -१,२,१] सँग सब भन्दा ठूलो रकम =। छ।

nums = [-1]
-1

दृष्टिकोण १ (विभाजन र विजय)

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

केस 1:
अधिकतम subarray एर्रेको बाँया आधामा पूर्ण रूपमा रहेको छ।
केस 2:
अधिकतम subarray एर्रेको दायाँ आधामा पूर्ण रूपमा रहेको छ।
केस 3:
अधिकतम सुबर्रेको आंशिक भाग बायाँ आधामा निहित छ र यसको आंशिक भाग दोस्रो आधामा रहेको छ (जस्तै सुभ्रे एर्रेको मध्य तत्व पार गर्दैछ)

जस्तो कि हामी केस १ र केस २ देख्न सक्दछौं, N / २ आकारको एरेको सबप्रोब्लम भनेको मुख्य समस्याको रूपमा समान परिभाषा छ। जहाँ एन वर्तमान एर्रेको आकार छ। त्यसैले हामी सजीलै गर्न सक्छौं दोहोरिन्छ एर्रेको दुई भागमा प्रकार्य।
अब मुख्य भाग केस 3 हो जुन हामीले हालको फंक्शनमा समाधान गर्नुपर्नेछ र त्यसपछि हामी यी cases केसमध्ये अधिकतम रकम फिर्ता गर्न सक्छौं।

हामी केस 3 को लागि कसरी समाधान गर्न सक्छौं हेरौं:

मानौं हामीसँग एर्रे = [-२,१, -2,1, -१,२,१, -3,4]
हामी मध्य सूचकांक यसलाई दुई बराबर भागमा विभाजित गर्न फेला पार्दछौं।
मध्य सूचकांक = (० +)) / २ =।

अधिकतम सुबर्रे लीटकोड समाधान

मामला 3 ले भनेको छ कि अधिकतम योगले मध्य तत्व पार गर्दछ। त्यसैले हामी अधिकतम योग मध्यबाट सुरू गरेर बाँया पट्टि अन्त्य हुने फेला पार्ने छौं। त्यस्तै गरी हामी अधिकतम योग (मध्य +१) मा सुरू गरेर दायाँ पट्टि अन्त्य हुने फेला पार्नेछौं। यस तरीकाले हामी अधिकतम सबभरि फेला पार्नेछौं जुन केस 1 का लागि मध्य सीमा पार गर्दैछ।

एल्गोरिथ्म:

  • एर्रेलाई दुई भागमा विभाजन गर्नुहोस्।
  • पुनरावृत्तिक रूपमा बायाँ सबर्रेको लागि अधिकतम सब्रे्रे योग फेला पार्नुहोस्।
  • पुन: पुनरावृत्ति दायाँ सबभ्रेको लागि अधिकतम सब्रे्रे योग फेला पार्नुहोस्।
  • मध्यबिन्दु पार गर्ने अधिकतम subarray योग फेला पार्नुहोस्।
  • अधिकतम तीन योगफल फर्काउनुहोस्।

अधिकतम सुबर्रे लेटकोड समाधानको लागि कार्यान्वयन

C ++ कार्यक्रम

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

int helper(int i,int j, vector<int>& nums)
{
    if(i==j) return nums[i];
    int left_cross=INT_MIN, right_cross=INT_MIN;

    int mid= (i+j)/2;
    int cur=0;
    for(int k=mid+1;k<=j;k++)
    {
        cur+= nums[k];
        right_cross= max(right_cross,cur);
    }

    cur=0;
    for(int k=mid;k>=i;k--)
    {
        cur+= nums[k];
        left_cross= max(left_cross,cur);
    }

    int cross_sum = left_cross + right_cross;
    int left_sum  = helper(i,mid,nums);
    int right_sum = helper(mid+1,j,nums);

    return max( cross_sum , max(left_sum , right_sum) );
}

int maxSubArray(vector<int>& nums) {
    return helper(0,nums.size()-1,nums);
}

int main() 
{
    vector<int> nums={-2,1,-3,4,-1,2,1,-5,4};
    cout<< maxSubArray(nums) <<endl;
    return 0; 
}
6

जावा कार्यक्रम

class Rextester{
    
  static int helper(int i,int j, int[] nums)
    { 
        if(i==j) return nums[i];       
        int left_cross=Integer.MIN_VALUE, right_cross=Integer.MIN_VALUE;
        
        int mid= (i+j)/2;
        int cur=0;
        for(int k=mid+1;k<=j;k++)
        {
            cur+= nums[k];
            right_cross= Math.max(right_cross,cur);
        }
        
        cur=0;
        for(int k=mid;k>=i;k--)
        {
            cur+= nums[k];
            left_cross= Math.max(left_cross,cur);
        }
        
        int cross_sum=  left_cross + right_cross; 
        int left_sum = helper(i,mid,nums);
        int right_sum = helper(mid+1,j,nums);
        
        return Math.max( cross_sum , Math.max(left_sum , right_sum) );        
    }
    
    public static int maxSubArray(int[] nums) {
        return helper(0,nums.length-1,nums);
    }
    
  public static void main(String args[])
    {
       	int[] nums={-2,1,-3,4,-1,2,1,-5,4};
    System.out.println(maxSubArray(nums));
    }
}
6

अधिकतम सुबर्रे लेटकोड समाधानको लागि जटिलता विश्लेषण

समय जटिलता

O (NlogN): विभाजित र विजय मा वास्तव मा हामी समस्या N / 2 आकार को दुई बराबर भागमा विभाजित गर्दै छौं। फेरि यो N / 4 को आकार मा विभाजित छ र यस्तै। त्यसकारण पुनरावृत्तिको गहिराइ स्तर लग एन हुनेछ जहाँ एरेको आकार १ हुनेछ र हामी त्यहाँबाट फर्कदैछौं। प्रत्येक स्तरमा हामी O (n) कार्य गर्दैछौं त्यसैले कुल समय जटिलता O (NlogN) हुनेछ। यहाँ पुनरावृत्ति सम्बन्ध छ

ठाउँ जटिलता 

O (logN): लग एन स्पेस पुनरावर्तन स्ट्याकको लागि प्रयोग गरिन्छ।

 

दृष्टिकोण २ (कडानेको विधि)

Kadane विधि सब एरे योग को लागी एक प्रसिद्ध एल्गोरिथ्म हो। यस विधिमा हामी केवल एक पटक दिइएको इनपुट एर्रेमा पुनरावृत्ति गर्छौं। हामी शुन्य मानको साथ सुरुमा हालको योग लिन्छौं र प्रत्येक तत्व मार्गमा थप्दछौं। हामी प्रत्येक तत्त्वलाई वर्तमान योगमा थप्छौं यदि यदि अघिल्लो वर्तमान योग negativeणात्मक छैन वा अन्यथा हामी केवल निरन्तरता तोड्छौं र वर्तमान योगफललाई वर्तमान तत्वको साथ अपडेट गर्दछौं। यसको साथ प्रत्येक स्थितिमा हामी जाँच गर्दछौं कि वर्तमान योग्ता पनि ग्लोबल अधिकतम छ वा छैन र त्यस अनुसार ग्लोबल अधिकतम अपडेट गर्दछौं।

एल्गोरिथ्म:

  • ग्लोबल अधिकतम भण्डार गर्न एक चर बनाउनुहोस्। सबैभन्दा नकारात्मक नम्बर (INT_MIN) को साथ शुरू गर्नुहोस्।
  • हालको योग भण्डार गर्न भेरिएबल सिर्जना गर्नुहोस्। शून्यसँग आरम्भ गर्नुहोस्।
  • एरमा बाँयाबाट दाँया लुप चलाउनुहोस्। यदि हालको योग negativeणात्मक भयो भने यसलाई ० मानको साथ अपडेट गर्नुहोस्।
  • हालको तत्वलाई वर्तमान योगमा थप्नुहोस् र ग्लोबल अधिकतम अपडेट गर्नुहोस् यदि हालको योग वैश्विक अधिकतम भन्दा ठूलो छ।
  • ग्लोबल अधिकतम फिर्ता गर्नुहोस्।

अधिकतम सुबर्रे लेटकोड समाधानको लागि कार्यान्वयन

C ++ कार्यक्रम

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

int maxSubArray(vector<int>& nums) 
{
    int max_sum=INT_MIN;
    int cur=0;
    for(auto x:nums)
    {
        if(cur<0) cur=0;
        cur += x;
        max_sum =  max(max_sum , cur);
    }
    return max_sum;
}

int main() 
{
    vector<int> nums={-2,1,-3,4,-1,2,1,-5,4};
    cout<< maxSubArray(nums) <<endl;
    return 0; 
}
6

जावा कार्यक्रम

class Rextester{
  
    public static int maxSubArray(int[] nums) 
    {
        int max_sum = Integer.MIN_VALUE;
        int cur=0;
        for(int x:nums)
        {
            if(cur<0) cur=0;
            cur += x;
            max_sum =  Math.max(max_sum , cur);
        }
        return max_sum;
    }
    
  public static void main(String args[])
    {
       	int[] nums={-2,1,-3,4,-1,2,1,-5,4};
    System.out.println(maxSubArray(nums));
    }
}
6

अधिकतम सुबर्रे लेटकोड समाधानको लागि जटिलता विश्लेषण

समय जटिलता

O (N): किनकि यो एर्रेमा एक पास एल्गोरिथ्म हो।

ठाउँ जटिलता 

O (१): कुनै अतिरिक्त मेमोरी प्रयोग गरिएको छैन।