அதிகபட்ச சுபரே லீட்கோட் தீர்வு  


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது அடோப் அமேசான் ஆப்பிள் ப்ளூம்பெர்க் ByteDance சிஸ்கோ பேஸ்புக் கோல்ட்மேன் சாக்ஸ் கூகிள் ஜேபி மோர்கன் லின்க்டு இன் மைக்ரோசாப்ட் ஆரக்கிள் பேபால் Paytm கிழித்து
அணி குறியீட்டு பிரித்து வெல்லுங்கள் டைனமிக் புரோகிராமிங் பேட்டி நேர்காணல் தயாரிப்பு லீட்கோட் LeetCodeSolutions

சிக்கல் அறிக்கை  

ஒரு முழு வரிசை வரிசை எண்களைக் கொடுத்து, தொடர்ச்சியைக் கண்டறியவும் subarray (குறைந்தது ஒரு எண்ணைக் கொண்டது) இது மிகப்பெரிய தொகையைக் கொண்டுள்ளது மற்றும் அதன் தொகையைத் தருகிறது.

உதாரணமாக

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 அளவிலான வரிசையின் துணைப் பிரச்சினையாகும். N என்பது தற்போதைய வரிசையின் அளவு. எனவே நாம் வெறுமனே முடியும் மீண்டும் நிகழ்கிறது வரிசையின் இரண்டு பகுதிகளுக்கு மேல் செயல்பாடு.
இப்போது முக்கிய பகுதி வழக்கு 3 ஆகும், இது தற்போதைய செயல்பாட்டில் நாம் தீர்க்க வேண்டும், பின்னர் இந்த 3 நிகழ்வுகளில் அதிகபட்ச தொகையை திருப்பித் தரலாம்.

மேலும் காண்க
N-ary மரத்தில் கொடுக்கப்பட்ட முனையின் உடன்பிறப்புகளின் எண்ணிக்கை

வழக்கு 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

அதிகபட்ச சுபரே லீட்கோட் தீர்வுக்கான சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

O (NlogN): பிளவு மற்றும் வெற்றியில் உண்மையில் நாம் சிக்கலை N / 2 அளவு இரண்டு சம பகுதிகளாக பிரிக்கிறோம். மீண்டும் அது N / 4 மற்றும் பலவற்றில் பிரிக்கப்படுகிறது. எனவே ஆழ்ந்த அளவிலான மறுநிகழ்வு logN ஆக இருக்கும், அங்கு வரிசையின் அளவு 1 ஆக இருக்கும், நாங்கள் அங்கிருந்து திரும்பி வருகிறோம். ஒவ்வொரு மட்டத்திலும் நாம் O (n) பணியைச் செய்கிறோம், எனவே மொத்த நேர சிக்கலானது O (NlogN) ஆக இருக்கும். இங்கே மீண்டும் மீண்டும் உறவு உள்ளது

மேலும் காண்க
சொல்லைச் சேர்த்துத் தேடுங்கள் - தரவு கட்டமைப்பு வடிவமைப்பு லீட்கோட்

விண்வெளி சிக்கலானது 

O (logN): logN இடம் மறுநிகழ்வு அடுக்குக்கு பயன்படுத்தப்படுகிறது.

 

அணுகுமுறை 2 (கடானின் முறை)  

கடானின் முறை துணை வரிசை தொகைக்கு ஒரு பிரபலமான வழிமுறையாகும். இந்த முறையில், கொடுக்கப்பட்ட உள்ளீட்டு வரிசைக்கு ஒரு முறை மீண்டும் சொல்கிறோம். நாம் தற்போதைய தொகையை ஆரம்பத்தில் மதிப்பு பூஜ்ஜியத்துடன் எடுத்து பாதையில் ஒவ்வொரு உறுப்புகளையும் சேர்க்கிறோம். முந்தைய நடப்புத் தொகை எதிர்மறையாக இல்லாவிட்டால் ஒவ்வொரு உறுப்புகளையும் தற்போதைய தொகைக்குச் சேர்க்கிறோம் அல்லது இல்லையெனில் தொடர்ச்சியை உடைத்து தற்போதைய தொகையை தற்போதைய உறுப்புடன் புதுப்பிக்கிறோம். ஒவ்வொரு நிலையிலும் அதனுடன் தற்போதைய தொகை உலகளாவிய அதிகபட்சமா இல்லையா என்பதைச் சரிபார்த்து, அதற்கேற்ப உலகளாவிய அதிகபட்சத்தைப் புதுப்பிக்கிறோம்.

அல்காரிதம்:

  • உலகளாவிய அதிகபட்சத்தை சேமிக்க ஒரு மாறியை உருவாக்கவும். மிகவும் எதிர்மறை எண்ணுடன் (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): கூடுதல் நினைவகம் பயன்படுத்தப்படவில்லை.

1