Maksimum məhsul subarray

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Bir sıra n ədəd ədədi verilmiş, verilmiş bitişik subarraydan alınan maksimum məhsulu tapın array.

Nümunələr

Input
arr [] = {-2, -3, 0, -2, -40}
Buraxılış
80

Input
arr [] = {5, 10, 6, -2, 1}
Buraxılış
300

Input
arr [] = {-1, -4, -10, 0, 70}
Buraxılış
70

Maksimum məhsul subarray üçün alqoritm

Verilən məsələ Kadane alqoritminin bir dəyişikliyidir, üç dəyişəni təyin edin maxTillNow, minTillNow və max, burada,
maxTillNow -> Bu indeks daxil olmaqla bu indeksə qədər maksimum məhsul
minTillNow -> Bu indeks daxil olmaqla bu indeksə qədər minimum məhsul
max -> maksimum məhsul

1. MaxTillNow, minTillNow və max kimi arr [0] kimi başlayın.
2. Dizini 1-dən başlayaraq cərgəni keçin.
3. Mövcud element mənfi olduqda maxTillNow və minTillNow dəyişdirin.
4. MaxTillNow'u maksimum arr [i] və (maxTillNow * arr [i]) kimi yeniləyin.
5. MinTillNow-u minimum arr [i] və (minTillNow * arr [i]) kimi yeniləyin.
6. Ayrıca, maksimumu maksimum və maxTillNow kimi yeniləyin.
7. Keçidin sonunda maks.

Maksimum məhsul subarray üçün izah

Bir nümunəyə baxaq,
arr [] = {5, 10, 6, -2, 1}

Step 1

maxTillNow = 5, minTillNow = 5 və max = 5

Step 2

3-6 addımları təkrarlayın.

3-6 addımlar

Təkrarlama 1
arr [1] = 10
maxTillNow = 5 və minTillNow = 5
MaxTillNow-u yeniləyin,
maxTillNow = maksimum (arr [1], maxTillNow * arr [1]) = 50
MinTillNow yeniləyin,
minTillNow = minimum (arr [1], minTillNow * arr [1] = 10
Maksimumu yeniləyin,
max = maksimum (max, maxTillNow) = 50

Təkrarlama 2
arr [2] = 6
maxTillNow = 50 və minTillNow = 10
MaxTillNow-u yeniləyin,
maxTillNow = maksimum (arr [2], maxTillNow * arr [2]) = 300
MinTillNow yeniləyin,
minTillNow = minimum (arr [2], minTillNow * arr [2]) = 6
Maksimumu yeniləyin,
max = maksimum (max, maxTillNow) = 300

Təkrarlama 3
arr [3] = -2
maxTillNow = 6 və minTillNow = 300 (arr [3] kimi dəyişdirin mənfi)
MaxTillNow-u yeniləyin,
maxTillNow = maksimum (arr [3], maxTillNow * arr [3]) = -2
MinTillNow yeniləyin,
minTillNow = minimum (arr [3], minTillNow * arr [3]) = -600
Maksimumu yeniləyin,
max = maksimum (max, maxTillNow) = 300

Təkrarlama 4
arr [4] = 1
maxTillNow = -2 və minTillNow = -600
MaxTillNow-u yeniləyin,
maxTillNow = maksimum (arr [4], maxTillNow * arr [4]) = 1
MinTillNow yeniləyin,
minTillNow = minimum (arr [4], minTillNow * arr [4]) = -600
Maksimumu yeniləyin,
max = maksimum (max, maxTillNow) = 300

Step 7

Maksimum dəyər məhsul subarray dəyəri 300-dür.

Pin

Maksimum məhsul subarray üçün JAVA kodu

public class MaximumProductSubarray {
    private static int maxProduct(int[] arr) {
        int n = arr.length;
        // Initialise maxTillNow, minTillNow and max as arr[0]
        int maxTillNow = arr[0], minTillNow = arr[0], max = arr[0];
        // Start traversing the array from index 1
        for (int i = 1; i < n; i++) {
            // If current element is negative, swap maxTillNow and minTillNow
            if (arr[i] < 0) {
                int temp = maxTillNow;
                maxTillNow = minTillNow;
                minTillNow = temp;
            }
            
            // Update maxTillNow as maximum of arr[i] and (arr[i] * maxTillNow)
            maxTillNow = Math.max(arr[i], arr[i] * maxTillNow);
            // Update minTillNow as minimum of arr[i] and (arr[i] * minTillNow)
            minTillNow = Math.min(arr[i], arr[i] * minTillNow);
            
            // Update max as maximum of max and maxTillNow
            max = Math.max(max, maxTillNow);
        }
        
        // return max
        return max;
    }

    public static void main(String[] args) {
        // Example 1
        int arr[] = new int[] {-2, -3, 0, -2, -40};
        System.out.println(maxProduct(arr));

        // Example 2
        int arr2[] = new int[] {5, 10, 6, -2, 1};
        System.out.println(maxProduct(arr2));

        // Example 3
        int arr3[] = new int[] {-1, -4, -10, 0, 70};
        System.out.println(maxProduct(arr3));
    }
}

Maksimum məhsul subarray üçün C ++ kodu

#include <bits/stdc++.h>
using namespace std;

int maxProduct(int *arr, int n) {
    // Initialise maxTillNow, minTillNow and max as arr[0]
    int maxTillNow = arr[0], minTillNow = arr[0], max = arr[0];
    // Start traversing the array from index 1
    for (int i = 1; i < n; i++) {
        // If current element is negative, swap maxTillNow and minTillNow
        if (arr[i] < 0) {
            int temp = maxTillNow;
            maxTillNow = minTillNow;
            minTillNow = temp;
        }
        
        // Update maxTillNow as maximum of arr[i] and (arr[i] * maxTillNow)
        maxTillNow = std::max(arr[i], arr[i] * maxTillNow);
        // Update minTillNow as minimum of arr[i] and (arr[i] * minTillNow)
        minTillNow = std::min(arr[i], arr[i] * minTillNow);
        
        // Update max as maximum of max and maxTillNow
        max = std::max(max, maxTillNow);
    }
    
    // return max
    return max;
}

int main() {
    // Example 1
    int arr[] = {-2, -3, 0, -2, -40};
    cout<<maxProduct(arr, 5)<<endl;
    
    // Example 2
    int arr2[] = {5, 10, 6, -2, 1};
    cout<<maxProduct(arr2, 5)<<endl;
    
    // Exmaple 3
    int arr3[] = {-1, -4, -10, 0, 70};
    cout<<maxProduct(arr3, 5)<<endl;
    
    return 0;
}

80
300
70

Mürəkkəblik təhlili

Zaman Mürəkkəbliyi = O (n)
Kosmik Mürəkkəblik = O (1) 
burada n - massivdəki elementlərin sayı.

References