મહત્તમ સુબાર્રે લીટકોડ સોલ્યુશન


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે એડોબ એમેઝોન સફરજન બ્લૂમબર્ગ ByteDance સિસ્કો ફેસબુક ગોલ્ડમૅન સૅશ Google જેપીમોર્ગન LinkedIn માઈક્રોસોફ્ટ ઓરેકલ પેપાલ પેટીએમ ઉબેર
અરે વિભાજીત અને વિજય ડાયનેમિક પ્રોગ્રામિંગ

સમસ્યા નિવેદન

પૂર્ણાંક એરે નંબર્સ આપ્યા, સુસંગત શોધો સબબ્રે (ઓછામાં ઓછું એક નંબર ધરાવતું) જેમાં સૌથી વધુ રકમ છે અને તેનો સરવાળો પરત કરે છે.

ઉદાહરણ

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

સમજૂતી:

[,, -4] માં સૌથી મોટી રકમ = 1,2,1 છે.

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

મહત્તમ સુબાર્રે લીટકોડ સોલ્યુશન માટે જટિલતા વિશ્લેષણ

સમય જટિલતા

O (NlogN): વિભાજન અને વિજયમાં ખરેખર આપણે સમસ્યાને N / 2 કદના બે સમાન ભાગોમાં વહેંચી રહ્યા છીએ. ફરીથી તે N / 4 ના કદમાં વિભાજીત થઈ રહ્યું છે અને આગળ. તેથી પુનરાવર્તનનું સૌથી levelંડો સ્તર લોગએન હશે જ્યાં એરેનું કદ 1 હશે અને અમે ત્યાંથી પાછા આવી રહ્યા છીએ. દરેક સ્તરે આપણે O (n) કાર્ય કરી રહ્યા છીએ તેથી કુલ સમય જટિલતા O (NlogN) હશે. અહીં પુનરાવર્તન સંબંધ છે

અવકાશ જટિલતા 

ઓ (લોગએન): લોગએન સ્પેસનો ઉપયોગ રિકર્ઝન સ્ટેક માટે થાય છે.

 

અભિગમ 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): કોઈ વધારાની મેમરીનો ઉપયોગ થતો નથી.