Ենթածրագրի առավելագույն լուծաչափը Leetcode


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Adobe Amazon խնձոր Bloomberg ByteDance Cisco facebook Goldman Sachs-ը Google JPMorgan LinkedIn Microsoft Պատգամախոս PayPal Paytm Uber
Դասավորություն Բաժանել եւ նվաճել Դինամիկ ծրագրավորում

Խնդիրի հայտարարություն

Հաշվի առնելով ամբողջ զանգվածի համարները, գտիր հարակիցը ենթաշերտ (պարունակում է առնվազն մեկ թիվ) որն ունի ամենամեծ գումարը և վերադարձնի իր գումարը:

Օրինակ

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

Բացատրությունը.

[4, -1,2,1] ամենամեծ գումարն ունի = 6:

nums = [-1]
-1

Մոտեցում 1 (բաժանիր և նվաճիր)

Այս մոտեցման ընթացքում մենք կքննարկենք այս խնդիրը լուծելու համար բաժանիր և հաղթիր տեխնիկայի մասին: Մենք փորձում ենք գտնել այդ հարակից ենթադասերը, որն ունի առավելագույն գումար: Այսպիսով, կարող ենք ասել, որ օպտիմալ ենթադասը կարող է լինել զանգվածի ցանկացած մասում: Այսպիսով, մենք պատրաստում ենք երեք դեպք, որոնք կներառեն բոլոր հնարավորությունները.

Case 1:
Max ենթավանդակը ամբողջությամբ գտնվում է զանգվածի ձախ կեսում:
Case 2:
Max ենթածրագիրը ամբողջովին տեղավորված է զանգվածի աջ կեսում:
Case 3:
Առավելագույն ենթախմբի մասնակի մասը գտնվում է ձախ կեսում, իսկ դրա մեկ այլ մասն էլ գտնվում է երկրորդ կեսում (այսինքն `ենթախմբը հատում է զանգվածի միջին տարրը)

Ինչպես տեսնում ենք, 1-ին և 2-րդ դեպքերը հիմնականում N / 2 չափի զանգվածի ենթածրագիր են, որոնք ունեն նույն սահմանումը, ինչպես հիմնական խնդիրը: Որտեղ N է ընթացիկ զանգվածի չափը: Այսպիսով, մենք կարող ենք պարզապես կրկնվում է զանգվածի երկու կեսերի գործառույթը:
Այժմ հիմնական մասը 3-րդ դեպքն է, որը մենք պետք է լուծենք ընթացիկ գործառույթով, և ապա այս 3 դեպքերից կարող ենք վերադարձնել առավելագույն գումարը:

Տեսնենք, թե ինչպես կարող ենք լուծել 3-րդ դեպքի համար.

Ենթադրենք, որ մենք ունենք զանգված = [-2,1, -3,4, -1,2,1, -5,4]
Մենք գտնում ենք միջին ցուցանիշը `այն բաժանելու համար երկու հավասար կեսերի:
միջին ինդեքս = (0 + 9) / 2 = 4

Ենթածրագրի առավելագույն լուծաչափը Leetcode

Քանի որ 3-րդ դեպքն ասում է, որ առավելագույն գումարը հատելու է միջին տարրը: Այսպիսով, մենք կփորձենք գտնել առավելագույն գումարը սկսած կեսերից և ավարտված ձախ կողմում: Նմանապես, մենք կգտնենք առավելագույն գումարը սկսած (կես + 1) -ից և ավարտված աջ կողմում: Այս կերպ մենք կգտնենք առավելագույն ենթաշղթան, որն անցնում է 3-րդ գործի միջին սահմանը:

Ալգորիթմ

  • Theանգվածը բաժանեք երկու մասի:
  • Պարբերաբար գտեք ստորին զանգվածի առավելագույն գումարը ձախ ենթախմբի համար:
  • Ռեկուրսիվորեն գտեք ենթածրագրի առավելագույն գումարը աջ ենթահաշվի համար:
  • Գտեք ենթածրագրի առավելագույն գումարը, որն անցնում է միջին կետը:
  • Վերադարձեք առավելագույնը երեք գումարից վեր:

Իրականացում ենթածրագրի առավելագույն Leetcode լուծման համար

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

Java ծրագիր

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

Բարդության վերլուծություն ենթածրագրի առավելագույն Leetcode լուծման համար

Timeամանակի բարդություն

O (NlogN): Բաժանիր և նվաճիր իրականում, մենք խնդիրը բաժանում ենք N / 2 չափի երկու հավասար կեսերի: Կրկին այն բաժանվում է N / 4 չափի և այլն: Հետևաբար, հետադարձման ամենախորը մակարդակը կգրանցվի, որտեղ զանգվածի չափը կլինի 1, և մենք վերադառնում ենք այնտեղից: Յուրաքանչյուր մակարդակում մենք կատարում ենք O (n) առաջադրանք, ուստի ժամանակի ընդհանուր բարդությունը կլինի O (NlogN): Այստեղ կրկնության հարաբերությունն է

Տիեզերական բարդություն 

O (logN): logN տարածքն օգտագործվում է ռեկուրսիայի բուրգերի համար:

 

Մոտեցում 2 (Կադանեի մեթոդը)

Կադանի մեթոդը ենթ զանգվածի գումարի հայտնի ալգորիթմ է: Այս մեթոդով մենք պարզապես մեկ անգամ կրկնվում ենք տրված մուտքային զանգվածի վրա: Մենք սկզբում վերցնում ենք ընթացիկ գումար `զրոյական արժեքով և յուրաքանչյուր տարր ավելացնում ճանապարհին: Մենք յուրաքանչյուր տարր ավելացնում ենք ընթացիկ գումարին, եթե նախորդ ընթացիկ գումարը բացասական չէ կամ հակառակ դեպքում մենք պարզապես կոտրում ենք շարունակականությունը և ընթացիկ գումարը թարմացնում ընթացիկ տարրի հետ: Յուրաքանչյուր դիրքում դրան զուգահեռ մենք ստուգում ենք ՝ արդյո՞ք ընթացիկ գումարը նույնպես գլոբալ առավելագույն է, թե ոչ և ըստ դրա թարմացնում ենք գլոբալ առավելագույնը:

Ալգորիթմ

  • Ստեղծեք փոփոխական `գլոբալ առավելագույնը պահելու համար: Նախաձեռնեք առավելագույն բացասական թվով (INT_MIN):
  • Ստեղծեք փոփոխական `ընթացիկ գումարը պահելու համար: Նախնականացնել զրոյով:
  • Անցեք մի օղակ ձախից աջ զանգվածի վրայով: Եթե ​​ընթացիկ գումարը դարձել է բացասական, ապա այն թարմացրու 0 արժեքով:
  • Ընթացիկ գումարին ավելացրեք ընթացիկ տարրը և թարմացրեք գլոբալ առավելագույնը, եթե ընթացիկ գումարն ավելի մեծ է, քան գլոբալ առավելագույնը:
  • Վերադարձեք համաշխարհային առավելագույնը:

Իրականացում ենթածրագրի առավելագույն Leetcode լուծման համար

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

Java ծրագիր

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

Բարդության վերլուծություն ենթածրագրի առավելագույն Leetcode լուծման համար

Timeամանակի բարդություն

ՎՐԱ) : Քանի որ դա զանգվածի վրա մեկ անցման ալգորիթմ է:

Տիեզերական բարդություն 

O (1): Լրացուցիչ հիշողություն չի օգտագործվում: