උපරිම සබ්රේ ලීට්කෝඩ් විසඳුම


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ ඇෙබෝ ඇමේසන් Apple ජංගම දුරකථන බ්ලූම්බර්ග් ByteDance සිස්කෝ ෆේස්බුක් ගෝල්ඩ්මන් සැක්ස් ගූගල් ජේපී මෝගන් LinkedIn මයික්රොසොෆ්ට් ඔරකල් පේපෑල් Paytm Uber
අරා බෙදන්න සහ ජය ගන්න ගතික වැඩසටහන්කරණය

ගැටළු ප්රකාශය

නිඛිල අරා අංකයක් ලබා දී, පරස්පර සොයා ගන්න 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 න් උපරිම මුදල ආපසු ලබා දිය හැකිය.

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) වේ. මෙන්න පුනරාවර්තන සම්බන්ධතාවය

අභ්‍යවකාශ සංකීර්ණතාව 

ඕ (ලොග්එන්): logN අවකාශය පුනරාවර්තන සිරස් සඳහා භාවිතා කරයි.

 

ප්රවේශය 2 (කඩනේගේ ක්රමය)

කඩනේගේ ක්‍රමය උප අරා එකතුව සඳහා ප්‍රසිද්ධ ඇල්ගොරිතමයකි. මෙම ක්‍රමයේදී අපි දී ඇති ආදාන අරාව හරහා එක් වරක් නැවත කියමු. අපි මුලින් ශුන්‍ය අගයක් සහිත වත්මන් මුදලක් ගෙන මාර්ගයේ එක් එක් මූලද්‍රව්‍ය එකතු කරමු. පෙර ධාරා එකතුව negative ණ නොවේ නම් අපි එක් එක් මූලද්‍රව්‍යය වත්මන් එකතුවට එකතු කරමු. එසේ නොමැතිනම් අපි අඛණ්ඩතාව බිඳ දමා වත්මන් මූලද්‍රව්‍යය සමඟ වත්මන් මුදල යාවත්කාලීන කරමු. ඒ සමඟම සෑම ස්ථානයකදීම අපි වත්මන් මුදල ගෝලීය උපරිම ද නැද්ද යන්න පරීක්ෂා කර බලා ඒ අනුව ගෝලීය උපරිමය යාවත්කාලීන කරමු.

ඇල්ගොරිතම:

  • ගෝලීය උපරිමය ගබඩා කිරීම සඳහා විචල්‍යයක් සාදන්න. බොහෝ negative ණ සංඛ්‍යාවක් (INT_MIN) සමඟ ආරම්භ කරන්න.
  • වත්මන් මුදල ගබඩා කිරීම සඳහා විචල්‍යයක් සාදන්න. බිංදුව සමඟ ආරම්භ කරන්න.
  • අරාව හරහා වමේ සිට දකුණට ලූපයක් ධාවනය කරන්න. වත්මන් මුදල negative ණ වී ඇත්නම් එය 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): අමතර මතකයක් භාවිතා නොවේ.