最大產品子陣列


難度級別
經常問 亞馬遜 蘋果 彭博社 Facebook 谷歌 Microsoft微軟
排列 動態編程

給定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. 遍歷結束時,返回最大值。

最大乘積子數組的說明

考慮一個例子,
arr [] = {5,10,6,-2,1}

步驟

maxTillNow = 5,minTillNow = 5,max = 5

步驟

重複步驟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
更新最大值
最大值=最大值(max,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
更新最大值
最大值=最大值(max,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
更新最大值
最大值=最大值(max,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
更新最大值
最大值=最大值(max,maxTillNow)= 300

步驟

乘積子數組的最大值為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是數組中元素的數量。

參考