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


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

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

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

Օրինակ

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): Այստեղ կրկնության հարաբերությունն է

Տես նաեւ,
Ավելացնել և որոնել բառը - տվյալների կառուցվածքի ձևավորում LeetCode

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

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ամանակի բարդություն

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

Տես նաեւ,
Երեք անընդմեջ գործակիցների Leetcode լուծում

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

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

1