Μέγιστη λύση Leetcode Subarray


Επίπεδο δυσκολίας Εύκολος
Συχνές ερωτήσεις πλίθα αμαζόνα μήλο 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 (Διαίρεση και κατάκτηση)

Σε αυτήν την προσέγγιση θα συζητήσουμε για την τεχνική διαίρεσης και κατάκτησης για την επίλυση αυτού του προβλήματος. Προσπαθούμε να βρούμε αυτό το συνεχόμενο υπόγειο που έχει το μέγιστο άθροισμα. Μπορούμε λοιπόν να πούμε ότι το βέλτιστο subarray μπορεί να βρίσκεται σε οποιοδήποτε μέρος του πίνακα. Έτσι κάνουμε τρεις περιπτώσεις που θα καλύψουν όλες τις δυνατότητες:

Υπόθεση 1:
Το Max subarray βρίσκεται εντελώς στο αριστερό μισό του πίνακα.
Υπόθεση 2:
Το Max subarray βρίσκεται εντελώς στο δεξί μισό του πίνακα.
Υπόθεση 3:
Μερικό τμήμα του max subarray βρίσκεται στο αριστερό μισό και ένα άλλο τμήμα του βρίσκεται στο δεύτερο μισό (δηλαδή η subarray διασχίζει το μεσαίο στοιχείο της συστοιχίας)

Όπως μπορούμε να δούμε την περίπτωση 1 και η περίπτωση 2 είναι βασικά ένα υποπρόβλημα της συστοιχίας μεγέθους Ν / 2 που έχει τον ίδιο ορισμό με το κύριο πρόβλημα. Όπου N είναι το μέγεθος του τρέχοντος πίνακα. Έτσι μπορούμε απλά επαναλαμβάνεται η συνάρτηση σε δύο μισά του πίνακα.
Τώρα το κύριο μέρος είναι η περίπτωση 3 την οποία πρέπει να λύσουμε στην τρέχουσα συνάρτηση και στη συνέχεια μπορούμε να επιστρέψουμε το μέγιστο ποσό από αυτές τις 3 περιπτώσεις.

Ας δούμε πώς μπορούμε να λύσουμε την περίπτωση 3:

Ας υποθέσουμε ότι έχουμε πίνακα = [-2,1, -3,4, -1,2,1, -5,4]
Βρίσκουμε τον μέσο δείκτη για να τον χωρίσουμε σε δύο ίσα μισά.
μέσος δείκτης = (0 + 9) / 2 = 4

Μέγιστη λύση Leetcode Subarray

Όπως λέει η περίπτωση 3, το μέγιστο άθροισμα θα διασχίσει το μεσαίο στοιχείο. Θα προσπαθήσουμε λοιπόν να βρούμε το μέγιστο ποσό που αρχίζει στα μέσα και τελειώνει στην αριστερή πλευρά. Ομοίως, θα βρούμε το μέγιστο ποσό που ξεκινά από (μέσα + 1) και τελειώνει στη δεξιά πλευρά. Με αυτόν τον τρόπο θα βρούμε το max subarray που διασχίζει το μεσαίο όριο για την περίπτωση 3.

Αλγόριθμος:

  • Χωρίστε τον πίνακα σε δύο μισά.
  • Ανακαλύψτε αναδρομικά το μέγιστο άθροισμα subarray για το αριστερό subarray.
  • Βρείτε αναδρομικά το μέγιστο άθροισμα subarray για το δεξί subarray.
  • Βρείτε το μέγιστο άθροισμα subarray που διασχίζει το μεσαίο σημείο.
  • Επιστρέψτε το μέγιστο των τριών αθροισμάτων.

Εφαρμογή για τη μέγιστη λύση Leetcode 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

Πρόγραμμα 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 Subarray

Χρόνος πολυπλοκότητας

O (NlogN): Στην πραγματικότητα, διαιρούμε και κατακτώντας χωρίζουμε το πρόβλημα σε δύο ίσα μισά μεγέθους N / 2. Και πάλι διαιρείται σε μέγεθος N / 4 και ούτω καθεξής. Εξ ου και το βαθύτερο επίπεδο αναδρομής θα είναι logN όπου το μέγεθος του πίνακα θα είναι 1 και επιστρέφουμε από εκεί. Σε κάθε επίπεδο κάνουμε O (n) εργασία, επομένως η συνολική πολυπλοκότητα του χρόνου θα είναι O (NlogN). Εδώ είναι η σχέση υποτροπής

Διαστημική πολυπλοκότητα 

O (logN): Ο χώρος logN χρησιμοποιείται για στοίβα αναδρομής.

 

Προσέγγιση 2 (μέθοδος Kadane)

Η μέθοδος Kadane είναι ένας διάσημος αλγόριθμος για το άθροισμα δευτερεύοντος πίνακα. Σε αυτήν τη μέθοδο επαναλαμβάνουμε μία φορά πάνω από τον δεδομένο πίνακα εισαγωγής. Παίρνουμε ένα τρέχον άθροισμα αρχικά με την τιμή μηδέν και προσθέτουμε κάθε στοιχείο στη διαδρομή. Προσθέτουμε κάθε στοιχείο στο τρέχον άθροισμα εάν το προηγούμενο τρέχον άθροισμα δεν είναι αρνητικό ή αλλιώς σπάμε τη συνέχεια και ενημερώνουμε το τρέχον άθροισμα με το τρέχον στοιχείο. Μαζί με αυτό σε κάθε θέση ελέγχουμε αν το τρέχον άθροισμα είναι επίσης παγκόσμιο μέγιστο ή όχι και ενημερώνουμε το συνολικό μέγιστο σύμφωνα με αυτό.

Αλγόριθμος:

  • Δημιουργήστε μια μεταβλητή για να αποθηκεύσετε το παγκόσμιο μέγιστο. Ξεκινήστε με τον πιο αρνητικό αριθμό (INT_MIN).
  • Δημιουργήστε μια μεταβλητή για να αποθηκεύσετε το τρέχον άθροισμα. Αρχίστε με μηδέν.
  • Εκτελέστε έναν βρόχο από αριστερά προς τα δεξιά πάνω από τον πίνακα. Εάν το τρέχον άθροισμα έχει γίνει αρνητικό, ενημερώστε το με την τιμή 0.
  • Προσθέστε το τρέχον στοιχείο στο τρέχον άθροισμα και ενημερώστε το συνολικό μέγιστο εάν το τρέχον άθροισμα είναι μεγαλύτερο από το παγκόσμιο μέγιστο.
  • Επιστρέψτε το συνολικό μέγιστο.

Εφαρμογή για τη μέγιστη λύση Leetcode Subarray

Πρόγραμμα 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 Subarray

Χρόνος πολυπλοκότητας

ΕΠΙ) : Δεδομένου ότι είναι ένας αλγόριθμος περάσματος πάνω από τον πίνακα.

Διαστημική πολυπλοκότητα 

O (1): Δεν χρησιμοποιείται επιπλέον μνήμη.