최대 제품 하위 배열

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

n 개의 정수 배열이 주어지면 주어진 항목의 연속 된 부분 배열에서 얻은 최대 곱을 찾습니다. 정렬.

예

입력
arr [] = {-2, -3, 0, -2, -40}
산출
80

입력
arr [] = {5, 10, 6, -2, 1}
산출
300

입력
arr [] = {-1, -4, -10, 0, 70}
산출
70

최대 제품 하위 배열을위한 알고리즘

주어진 문제는 Kadane의 알고리즘의 변형이며 maxTillNow, minTillNow 및 max 세 변수를 정의합니다. 여기서,
maxTillNow –>이 색인을 포함하여이 색인까지 최대 제품
minTillNow –>이 인덱스를 포함하여이 인덱스까지의 최소 제품
max –> 최대 제품

1. maxTillNow, minTillNow 및 max를 arr [0]로 초기화합니다.
2. 인덱스 1부터 시작하여 배열을 순회합니다.
3. 현재 요소가 음수이면 maxTillNow 및 minTillNow를 교체하십시오.
4. maxTillNow를 최대 arr [i] 및 (maxTillNow * arr [i])로 업데이트합니다.
5. minTillNow를 arr [i] 및 (minTillNow * arr [i])의 최소값으로 업데이트합니다.
6. 또한 max를 max 및 maxTillNow의 최대 값으로 업데이트하십시오.
7. 순회가 끝나면 max를 반환합니다.

최대 제품 하위 배열에 대한 설명

예를 들어,
arr [] = {5, 10, 6, -2, 1}

1단계

maxTillNow = 5, minTillNow = 5 및 최대 = 5

2단계

3 ~ 6 단계를 반복합니다.

3 ~ 6 단계

반복 1
arr [1] = 10
maxTillNow = 5 및 minTillNow = 5
maxTillNow 업데이트,
maxTillNow = 최대 (arr [1], maxTillNow * arr [1]) = 50
minTillNow 업데이트,
minTillNow = 최소값 (arr [1], minTillNow * arr [1] = 10
최대 업데이트,
최대 = 최대 (최대, maxTillNow) = 50

반복 2
arr [2] = 6
maxTillNow = 50 및 minTillNow = 10
maxTillNow 업데이트,
maxTillNow = 최대 (arr [2], maxTillNow * arr [2]) = 300
minTillNow 업데이트,
minTillNow = 최소값 (arr [2], minTillNow * arr [2]) = 6
최대 업데이트,
최대 = 최대 (최대, maxTillNow) = 300

반복 3
arr [3] = -2
maxTillNow = 6 및 minTillNow = 300 (arr [3]로 교체는 음수 임)
maxTillNow 업데이트,
maxTillNow = 최대 (arr [3], maxTillNow * arr [3]) = -2
minTillNow 업데이트,
minTillNow = 최소값 (arr [3], minTillNow * arr [3]) = -600
최대 업데이트,
최대 = 최대 (최대, maxTillNow) = 300

반복 4
arr [4] = 1
maxTillNow = -2 및 minTillNow = -600
maxTillNow 업데이트,
maxTillNow = 최대 (arr [4], maxTillNow * arr [4]) = 1
minTillNow 업데이트,
minTillNow = 최소값 (arr [4], minTillNow * arr [4]) = -600
최대 업데이트,
최대 = 최대 (최대, maxTillNow) = 300

7단계

최대 값 제품 하위 배열 값은 300입니다.

핀

최대 제품 하위 배열을위한 JAVA 코드

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));
    }
}

최대 제품 하위 배열을위한 C ++ 코드

#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

복잡성 분석

시간 복잡성 = O (N)
공간 복잡성 = O (1) 
여기서 n은 배열의 요소 수입니다.

참조