მაქსიმალური ქვეჯგუფის გამოცემა Leetcode


Რთული ტური Easy
ხშირად ეკითხებიან Adobe Amazon Apple Bloomberg ByteDance Cisco Facebook Goldman Sachs Google JPMorgan LinkedIn microsoft Oracle PayPal Paytm Uber
Array Დაყავი და იბატონე დინამიური პროგრამირება

პრობლემის განცხადება

მთელი მასივის რიცხვების გათვალისწინებით იპოვნეთ მიმდებარე ქვეჯგუფი (შეიცავს მინიმუმ ერთ რიცხვს), რომელსაც აქვს უდიდესი ჯამი და დააბრუნებს თავის ჯამს.

მაგალითი

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

მაქსიმალური ქვეჯგუფის გამოცემა Leetcode

როგორც მე –3 შემთხვევა ამბობს, რომ მაქსიმალური ჯამი გადალახავს შუა ელემენტს. ამიტომ შევეცდებით იპოვოთ მაქსიმალური თანხა შუა რიცხვებში დაწყებული და მარცხენა მხარეს დამთავრებული. ანალოგიურად, ჩვენ ნახავთ მაქსიმალურ თანხას, რომელიც იწყება (შუა +1) და მთავრდება მარჯვენა მხარეს. ამ გზით ჩვენ ვიხილავთ მაქსიმალურ ქვედანაყოფს, რომელიც გადალახავს შუა საზღვარს მე –3 შემთხვევისთვის.

ალგორითმი:

  • მასივი გაყავით ორ ნაწილად.
  • რეკურსიულად იპოვნეთ ქვეჯგუფის მაქსიმალური ჯამი მარცხენა ქვეჯგუფისთვის.
  • რეკურსიულად იპოვნეთ ქვეჯგუფის მაქსიმალური ჯამი მარჯვენა ქვეჯგუფისთვის.
  • იპოვეთ ქვეჯგუფის მაქსიმალური ჯამი, რომელიც კვეთს შუა წერტილს.
  • დააბრუნე მაქსიმუმ სამი თანხა.

განხორციელება Subarray მაქსიმალური 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

ჯავა პროგრამა

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 ამოხსნისთვის

დროის სირთულე

O (NlogN): გაყოფა და დაპყრობა სინამდვილეში ჩვენ ვყოფთ პრობლემას N / 2 ზომის ორ თანაბარ ნაწილად. ისევ ის იყოფა N / 4 ზომის და ა.შ. ამრიგად, დაბრუნების ყველაზე ღრმა დონე იქნება სისტემა, სადაც მასივის ზომა იქნება 1 და ჩვენ იქ ვბრუნდებით. თითოეულ დონეზე ვაკეთებთ O (n) დავალებას, ამიტომ დროის სირთულე იქნება O (NlogN). აქ არის რეციდივის მიმართება

სივრცის სირთულე 

O (logN): logN სივრცე გამოიყენება რეკურსიული დასტისთვის.

 

მიდგომა 2 (კადანის მეთოდი)

კადანეს მეთოდი არის ცნობილი მასივის ჯამური ალგორითმი. ამ მეთოდით ჩვენ მხოლოდ ერთხელ ვიმეორებთ მოცემული შეყვანის მასივს. ჩვენ ვიღებთ მიმდინარე ჯამს თავდაპირველად ნულის მნიშვნელობით და თითოეულ ელემენტს ვუმატებთ გზას. თითოეულ ელემენტს ვუმატებთ მიმდინარე ჯამს, თუ წინა მიმდინარე ჯამი არ არის უარყოფითი ან სხვაგვარად ჩვენ ვწყვეტთ უწყვეტობას და ვაახლებთ მიმდინარე ჯამს მიმდინარე ელემენტით. მასთან ერთად თითოეულ პოზიციაზე ვამოწმებთ არის თუ არა მიმდინარე თანხა გლობალური მაქსიმუმი თუ არა და ამის მიხედვით ვაახლებთ გლობალურ მაქსიმუმს.

ალგორითმი:

  • შექმენით ცვლადი გლობალური მაქსიმუმის შესანახად. ინიციალიზაცია ყველაზე უარყოფითი რიცხვით (INT_MIN).
  • შექმენით ცვლადი მიმდინარე თანხის შესანახად. ნულოვანი ინიციალიზაცია.
  • მარყუჟის გადატანა მარცხნიდან მარჯვნივ მასივზე. თუ მიმდინარე ჯამი გახდა უარყოფითი, განაახლეთ იგი 0 მნიშვნელობით.
  • მიმდინარე ელემენტს დაამატეთ მიმდინარე ელემენტი და განაახლეთ გლობალური მაქსიმუმი, თუ მიმდინარე თანხა უფრო მეტია, ვიდრე გლობალური მაქსიმუმი.
  • დააბრუნე გლობალური მაქსიმუმი.

განხორციელება Subarray მაქსიმალური 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

ჯავა პროგრამა

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 ამოხსნისთვის

დროის სირთულე

O (N): ვინაიდან ეს არის ერთი პასის ალგორითმი მასივზე.

სივრცის სირთულე 

O (1): დამატებითი მეხსიერება არ გამოიყენება.