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


कठिनाई स्तर आसान
में अक्सर पूछा एडोब वीरांगना सेब ब्लूमबर्ग ByteDance सिस्को Facebook गोल्डमैन सैक्स गूगल जेपी मॉर्गन लिंक्डइन माइक्रोसॉफ्ट ओरेकल पेपैल Paytm Uber
ऐरे विभाजन और जीत गतिशील प्रोग्रामिंग

समस्या का विवरण

पूर्णांक सरणी संख्याओं को देखते हुए, सन्निहित का पता लगाएं सबर्रे (जिसमें कम से कम एक संख्या होती है) जिसमें सबसे बड़ी राशि होती है और अपनी राशि लौटाता है।

उदाहरण

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

स्पष्टीकरण:

[4, -1,2,1] में सबसे बड़ा योग = 6 है।

nums = [-1]
-1

दृष्टिकोण 1 (विभाजित और जीतें)

इस दृष्टिकोण में हम इस समस्या को हल करने के लिए फूट डालो और जीतो तकनीक के बारे में चर्चा करेंगे। हम उस सन्निहित सबरे को खोजने की कोशिश कर रहे हैं, जिसमें अधिकतम राशि है। तो हम कह सकते हैं कि इष्टतम सब्रे सरणी के किसी भी हिस्से में झूठ बोल सकते हैं। तो हम तीन मामले बनाते हैं जो सभी संभावनाओं को कवर करेंगे:

प्रकरण 1:
अधिकतम सबरे सरणी के बाएं आधे हिस्से में पूरी तरह से निहित है।
प्रकरण 2:
अधिकतम सबरे सरणी के दाहिने आधे हिस्से में पूरी तरह से निहित है।
प्रकरण 3:
अधिकतम सबर्रे का आंशिक भाग बाएं आधे भाग में स्थित है और इसका दूसरा भाग दूसरे भाग में स्थित है (यानी सब्रे सरणी के मध्य तत्व को पार कर रहा है)

जैसा कि हम केस 1 देख सकते हैं और केस 2 मूल रूप से एन / 2 आकार की सरणी का एक उपप्रकार है जिसमें मुख्य समस्या के समान परिभाषा है। जहां N वर्तमान सरणी का आकार है। तो हम बस कर सकते हैं फिर से होता है सरणी के दो हिस्सों में समारोह।
अब मुख्य भाग 3 है जिसे हमें वर्तमान फ़ंक्शन में हल करना है और फिर हम इन 3 मामलों में से अधिकतम राशि वापस कर सकते हैं।

आइए देखें कि हम केस 3 के लिए कैसे हल कर सकते हैं:

मान लीजिए कि हमारे पास सरणी है = [-2,1, -3,4, -1,2,1, -5,4]
हम इसे दो समान हिस्सों में विभाजित करने के लिए मध्य सूचकांक पाते हैं।
मध्य सूचकांक = (0 + 9) / २ = ४

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

जैसा कि मामला 3 कह रहा है कि अधिकतम राशि मध्य तत्व को पार कर जाएगी। इसलिए हम अधिकतम राशि मध्य में शुरू करने और बाईं ओर समाप्त होने का प्रयास करेंगे। इसी तरह हम अधिकतम राशि (मध्य + 1) पर शुरू करेंगे और दाईं ओर समाप्त करेंगे। इस तरह हम अधिकतम सबरे को पाएंगे जो केस 3 के लिए मध्य सीमा को पार कर रहा है।

कलन विधि:

  • सरणी को दो हिस्सों में विभाजित करें।
  • बाईं सबर्रे के लिए पुन: अधिकतम सबर्रे योग का पता लगाएं।
  • राइट सबर्रे के लिए पुन: अधिकतम सबर्रे योग का पता लगाएं।
  • मध्य बिंदु को पार करने वाले अधिकतम उप-औसत योग का पता लगाएं।
  • उपरोक्त तीन रकमों की अधिकतम राशि लौटाएँ।

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

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। फिर से यह एन / 4 और इतने पर आकार में विभाजित है। इसलिए पुनरावृत्ति का सबसे गहरा स्तर logN होगा जहां सरणी का आकार 1 होगा और हम वहां से लौट रहे हैं। प्रत्येक स्तर पर हम O (n) कार्य कर रहे हैं इसलिए कुल समय जटिलता O (NlogN) होगी। यहाँ पुनरावृत्ति संबंध है

अंतरिक्ष जटिलता 

O (logN): logN स्पेस का उपयोग रिकर्सन स्टैक के लिए किया जाता है।

 

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

कडाने की विधि उप सरणी राशि के लिए एक प्रसिद्ध एल्गोरिथ्म है। इस विधि में हम दिए गए इनपुट ऐरे के ऊपर केवल एक बार पुनरावृति करते हैं। हम मूल्य शून्य के साथ शुरू में एक वर्तमान राशि लेते हैं और पथ में प्रत्येक तत्व को जोड़ते हैं। हम प्रत्येक तत्व को वर्तमान राशि में जोड़ते हैं यदि पिछली वर्तमान राशि नकारात्मक नहीं है या अन्यथा हम केवल निरंतरता को तोड़ते हैं और वर्तमान तत्व को वर्तमान तत्व के साथ अपडेट करते हैं। इसके साथ ही प्रत्येक स्थिति में हम जांचते हैं कि वर्तमान राशि भी वैश्विक अधिकतम है या नहीं और उसके अनुसार वैश्विक अधिकतम को अपडेट करें।

कलन विधि:

  • वैश्विक अधिकतम स्टोर करने के लिए एक चर बनाएं। सबसे नकारात्मक संख्या (INT_MIN) के साथ प्रारंभिक।
  • वर्तमान राशि को संग्रहीत करने के लिए एक चर बनाएं। शून्य के साथ प्रारंभिक।
  • सरणी पर बाएँ से दाएँ एक लूप चलाएँ। यदि वर्तमान योग ऋणात्मक हो गया है, तो इसे मान 0 के साथ अपडेट करें।
  • वर्तमान तत्व को वर्तमान योग में जोड़ें और वैश्विक अधिकतम को अपडेट करें यदि वर्तमान राशि वैश्विक अधिकतम से अधिक है।
  • वैश्विक अधिकतम लौटें।

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

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

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

समय जटिलता

पर) : चूंकि यह सरणी पर एक पास एल्गोरिथ्म है।

अंतरिक्ष जटिलता 

ओ (1): अतिरिक्त मेमोरी का उपयोग नहीं किया जाता है।