जास्तीत जास्त सुबर्रे लीटकोड सोल्यूशन


अडचण पातळी सोपे
वारंवार विचारले अडोब ऍमेझॉन सफरचंद ब्लूमबर्ग बाइट डान्स सिस्को फेसबुक गोल्डमन Sachs Google जेपी मॉर्गन, संलग्न मायक्रोसॉफ्ट ओरॅकल पोपल पेटीएम उबेर
अरे विभाजित आणि विजय डायनॅमिक प्रोग्रामिंग

समस्या विधान

पूर्णांक अ‍ॅरे क्रमांक दिले, त्यास संबद्ध शोधा सबअरे (कमीतकमी एक संख्या असलेली) ज्यात सर्वात मोठी बेरीज आहे आणि तिची बेरीज मिळवते.

उदाहरण

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 पाहत आहोत, ही मूळ समस्या N / 2 आकाराच्या अ‍ॅरेची मुख्य समस्या आहे. जेथे एन हा सध्याच्या अ‍ॅरेचा आकार आहे. तर आपण सहजपणे करू शकतो पुनरावृत्ती अ‍ॅरेच्या दोन भागांवर फंक्शन.
आताचा मुख्य भाग केस 3 आहे जो आपल्याला सध्याच्या फंक्शनमध्ये सोडवायचा आहे आणि मग आपण या 3 प्रकरणांमधून जास्तीत जास्त रक्कम परत मिळवू शकतो.

केस 3 चे निराकरण कसे करावे ते पाहू या:

समजा आपल्याकडे अ‍ॅरे = [-2,1, -3,4, -1,2,1, -5,4]
आम्ही त्याला दोन समान अर्ध्या भागासाठी मिड इंडेक्स शोधतो.
मध्य निर्देशांक = (0 + 9) / 2 = 4

जास्तीत जास्त सुबर्रे लीटकोड सोल्यूशन

जसे की केस 3 असे म्हणत आहे की जास्तीत जास्त बेरीज मध्यम घटक पार करेल. तर आम्ही जास्तीत जास्त बेरीज मध्यभागी प्रारंभ होण्यास आणि डावीकडील शेवटी शोधण्याचा प्रयत्न करू. त्याचप्रमाणे आपल्याला जास्तीत जास्त बेरीज (मध्य +1) पासून सुरू होणारी आणि उजवीकडील शेवटी दिसेल. अशाप्रकारे आपल्याला जास्तीत जास्त सबराय सापडेल जो केस 3 साठी मध्य सीमा ओलांडत असेल.

अल्गोरिदम:

  • अ‍ॅरेला दोन भागात विभाजित करा.
  • डावीकडील सब्रायसाठी पुनरावृत्तीसाठी जास्तीत जास्त सबरीची बेरीज शोधा.
  • उजवीक सब्रे्रेसाठी पुनरावृत्तीसाठी जास्तीत जास्त सब्रेरी बेरीज शोधा.
  • मध्यबिंदू ओलांडणारी जास्तीत जास्त सबरेची बेरीज शोधा.
  • जास्तीत जास्त तीन बेरीज परत करा.

जास्तीत जास्त सुबरी लेटकोड सोल्यूशनची अंमलबजावणी

सी ++ प्रोग्राम

#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

जास्तीत जास्त सुबरी लेटकोड सोल्यूशनसाठी जटिलता विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एनएलजीएन): विभाजित आणि विजयात प्रत्यक्षात आम्ही समस्येचे विभाजन N / 2 आकाराच्या दोन समान भागांमध्ये करीत आहोत. पुन्हा हे एन / of च्या आकारात विभागले जात आहे. म्हणून आवर्तीची सखोल पातळी लॉग एन होईल जिथे अ‍ॅरेचा आकार 4 असेल आणि आम्ही तेथून परत जात आहोत. प्रत्येक स्तरावर आम्ही ओ (एन) कार्य करत आहोत म्हणून एकूण वेळ जटिलता ओ (एनएलजीएन) असेल. येथे पुनरावृत्ती संबंध आहे

स्पेस कॉम्प्लेक्सिटी 

ओ (लॉगएन): लॉगएन स्पेस रिकर्सियन स्टॅकसाठी वापरली जाते.

 

अ‍ॅप्रोच २ (कडाणे यांची पद्धत)

कडणे यांची पद्धत सब अ‍ॅरेसाठी एक प्रसिद्ध अल्गोरिदम आहे. या पद्धतीत आम्ही दिलेल्या इनपुट अ‍ॅरेवर पुन्हा एकदा पुनरावृत्ती करू. आम्ही सुरुवातीस वर्तमान बेरीज शून्यसह घेतो आणि प्रत्येक घटक पथात जोडतो. मागील चालू बेरीज नकारात्मक नसल्यास आम्ही प्रत्येक घटकास वर्तमान बेरीजमध्ये जोडतो किंवा अन्यथा आम्ही फक्त सातत्य तोडून वर्तमान घटकासह वर्तमान बेरीज अद्यतनित करतो. त्यासह प्रत्येक स्थानावर आम्ही वर्तमान बेरीज देखील जागतिक कमाल आहे की नाही हे तपासतो आणि त्यानुसार जागतिक कमाल सुधारित करतो.

अल्गोरिदम:

  • ग्लोबल कमाल संचयित करण्यासाठी चल तयार करा. सर्वात नकारात्मक क्रमांकासह प्रारंभ करा (INT_MIN)
  • चालू बेरीज संचयित करण्यासाठी एक व्हेरिएबल तयार करा. शून्यासह आरंभ करा.
  • अ‍ॅरेवर डावीकडून उजवीकडे लूप चालवा. जर वर्तमान बेरीज नकारात्मक झाली असेल तर 0 मूल्यासह अद्यतनित करा.
  • वर्तमान बेरीज वर्तमान घटकामध्ये जोडा आणि जर वर्तमान बेरीज जास्तीत जास्त जास्त असेल तर जागतिक कमाल अद्यतनित करा.
  • जागतिक जास्तीत जास्त परत करा.

जास्तीत जास्त सुबरी लेटकोड सोल्यूशनची अंमलबजावणी

सी ++ प्रोग्राम

#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): कोणतीही अतिरिक्त मेमरी वापरली जात नाही.