د اعظمي سبریري لیټکوډ حل  


مشکل کچه په اسانۍ سره
په مکرر ډول دننه پوښتل کیږي ایڈوب ترلاسه کړئ Amazon مڼه د بلومبرګ ByteDance سیسکو فیسبوک ګولډمن Sachs د ګوګل JPMorgan LinkedIn د Microsoft سينه_پوښ وی.دا پیټم über
الگوريتم پیشه کوډ ورکول تقسیم او فتح متحرک برنامې مرکه د مرکې چمتووالی لیټ کوډ د لیټ کوډ حلونه

ستونزه بیان  

د عدد شمیره ورکړل شوه ، متناسب ومومئ سبارای (لږترلږه یوه شمیره لري) کوم چې ترټولو لوی رقم لري او خپل پیسې بیرته ورکوي.

بېلګه

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

وضاحت:

[4 ، -1,2,1،6،XNUMX] ترټولو لوی = XNUMX لري.

nums = [-1]
-1

تګلاره 1 (تقسیم او فتح کول)  

پدې لید کې به موږ د دې ستونزې حل کولو لپاره د تقسیم او فتح تخنیک په اړه بحث وکړو. موږ هڅه کوو چې هغه متقابل فرعي سربیره ولرو کوم چې اعظمي اندازه لري. نو موږ کولی شو ووایو چې مطلوب سبری ممکن د صف په کومې برخه کې موقعیت ولري. نو موږ درې قضیې جوړوو چې ټول امکانات به پوښښ وکړي:

قضیه 1:
میکس سبریري په بشپړ ډول د صف په کی of اړخ کې پروت دی.
قضیه 2:
د میکس سبریري په بشپړ ډول د صف په ښي نیم کې پروت دی.
قضیه 3:
د اعظمي subarray جزوي برخه په کی half لاس کې پرته ده او د هغې بله برخه په دوهمه نیمه کې پرته ده (د مثال په ډول subarray د صف د مینځ عنصر څخه تیریږی)

لکه څنګه چې موږ لیدلی شو 1 قضیه او قضیه 2 اساسا د N / 2 اندازه اندازې فرعي ستونزه ده چې اصلي ستونزه ورته ورته تعریف لري. چیرې چې N د اوسني صف اندازه ده. نو موږ کولی شو په ساده ډول تکرارول د سرې دوه برخې باندې فنکشن.
اوس اصلي برخه قضیه 3 ده چې موږ یې باید په اوسني فعالیت کې حل کړو او بیا موږ کولی شو د دې 3 قضیو څخه اعظمي اندازه بیرته ورکړئ.

هم وګوره
د nryry ونې کې د ورکړل شوي نوډ د ورو sو شمیر

راځئ چې وګورو چې څنګه د 3 قضیې لپاره حل کولی شو:

فرض کړئ چې موږ صف لري [[-2,1،3,4، -1,2,1،5,4، -XNUMX،XNUMX،XNUMX، -XNUMX،XNUMX]
موږ منځنی شاخص وموم چې دا په دوه مساوي برخو وویشئ.
منځنی شاخص = (0 + 9) / 2 = 4

د اعظمي سبریري لیټکوډ حل

لکه څنګه چې قضیه 3 ویل کیږي چې اعظمي برخه به د مینځ عنصر څخه تیر شي. نو موږ به هڅه وکړو چې اعظمي رقم په مینځ کې پیل او په کی left اړخ کې پای ته ورسیږو. په ورته ډول موږ به اعظمي اندازه په (منځنۍ + 1) پیل او په ښي اړخ کې پای ته ورسیږو. پدې توګه به موږ اعظمي مضافات ومومو کوم چې د قضیې 3 لپاره د مینځنۍ پولې څخه تیریږي.

الګوریتم:

  • سرنی په دوه برخو وویشئ.
  • په مکرر ډول د کی subې سبرای لپاره د اعظمي ساحې مجموعه ومومئ.
  • په مکرر ډول د ښیې subarray لپاره د subarray اعظمي جمع ومومئ.
  • د فرعي سر حد اعظمي برخه ومومئ چې د مینټ پوینټ څخه تیریږي.
  • د پورتنۍ درې شمیرو څخه اعظمي حد ته راستون شئ.

د اعظمي سبریري لیټکوډ حل لپاره پلي کول

C ++ برنامه

#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).
  • د اوسني جمع ذخیره کولو لپاره تغیرات جوړ کړئ. د صفر سره پیل کړئ.
  • له کي left څخه ښي څخه په صف باندې لوپ ولرئ. که اوسنی رقم منفي شوی وي نو دا د 0 ارزښت سره تازه کړئ.
  • اوسني عنصر په اوسني مجموعه کې اضافه کړئ او نړیوال اعظمي حد ته تازه کړئ که چیرې اوسنۍ مجموعه له نړیوالې اعظمي څخه زیاته وي
  • له نړیوالې اعظمي څخه بیرته راستون کړئ.

د اعظمي سبریري لیټکوډ حل لپاره پلي کول

C ++ برنامه

#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): اضافي حافظه ندي کارول شوې.