പരമാവധി സബ്‌റേ ലീട്ട്‌കോഡ് പരിഹാരം  


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു അഡോബി ആമസോൺ ആപ്പിൾ ബ്ലൂംബർഗ് ബൈറ്റ്ഡാൻസ് സിസ്കോ ഫേസ്ബുക്ക് ഗോൾഡ്മാൻ സാക്സ് ഗൂഗിൾ ചേസ് ലിങ്ക്ഡ് മൈക്രോസോഫ്റ്റ് ഒറാക്കിൾ പേപാൽ Paytm യൂബർ
അൽഗോരിതം അറേ കോഡിംഗ് ഭിന്നിപ്പിച്ചു കീഴടക്കുക ഡൈനാമിക് പ്രോഗ്രാമിംഗ് അഭിമുഖം അഭിമുഖം ലീട്ട് കോഡ് LeetCodeSolutions

പ്രശ്നം പ്രസ്താവന  

ഒരു സംഖ്യ അറേ സംഖ്യകൾ നൽകിയാൽ, തുടർച്ചയായത് കണ്ടെത്തുക സബറേ (കുറഞ്ഞത് ഒരു സംഖ്യയെങ്കിലും ഉൾക്കൊള്ളുന്നു), അതിൽ ഏറ്റവും വലിയ തുകയും അതിന്റെ തുകയും നൽകുന്നു.

ഉദാഹരണം

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 ന്റെ വലുപ്പത്തിലും മറ്റും വിഭജിക്കുന്നു. അതിനാൽ ഏറ്റവും ആഴത്തിലുള്ള ആവർത്തന ലോഗ് എൻ ആയിരിക്കും, അവിടെ അറേയുടെ വലുപ്പം 1 ആയിരിക്കും, ഞങ്ങൾ അവിടെ നിന്ന് മടങ്ങുകയാണ്. ഓരോ തലത്തിലും ഞങ്ങൾ O (n) ടാസ്‌ക് ചെയ്യുന്നു, അതിനാൽ മൊത്തം സമയ സങ്കീർണ്ണത O (NlogN) ആയിരിക്കും. ഇവിടെ ആവർത്തന ബന്ധം

ഇതും കാണുക
പദം ചേർത്ത് തിരയുക - ഡാറ്റ ഘടന രൂപകൽപ്പന ലീറ്റ്കോഡ്

ബഹിരാകാശ സങ്കീർണ്ണത 

O (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

പരമാവധി സബ്‌റേ ലീട്ട്‌കോഡ് പരിഹാരത്തിനായുള്ള സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (N): ഇത് അറേയ്‌ക്ക് മുകളിലുള്ള ഒരു പാസ് അൽഗോരിതം ആയതിനാൽ.

ഇതും കാണുക
തുടർച്ചയായ മൂന്ന് ആഡ്സ് ലീറ്റ്കോഡ് പരിഹാരം

ബഹിരാകാശ സങ്കീർണ്ണത 

O (1): അധിക മെമ്മറി ഉപയോഗിക്കുന്നില്ല.

1