最大產品子陣列


難度級別
經常問 亞馬遜 思科 Microsoft微軟 摩根士丹利(Morgan Stanley) Myntra PayU 時代互聯網 百會
排列

問題陳述

問題“最大乘積子數組”表明您得到了一個 排列 同時包含正數和負數的整數。 問題陳述要求找出子陣列的最大乘積。

arr[] = { 2, -2, 3, 5}
15

解釋

子數組中的元素是3和5,它們持有所有可能的子數組的最大乘積。

算法

1. Traverse the array from i = 0 to less than the value n(length of the given array).
  1. Check if arr[i] is greater than 0, if true
    1. Find out the maximumRange by multiplying each value of an array to itself.
    2. Find out the minimumRange between the product of minimumRange and arr[i] and 1.
    3. Mark flag is equal to 1.
  2. If the value of the array is equal to 0, then mark the minimum and maximum range to 1.
  3. Else find out the maximum between the product of minimumRange and arr[i] and 1 and find out the minimumRange by the product value of maximumRange and arr[i].
  4. If maxValue is less than the value of the maximumRange then store the value of maximumRange to maxValue.’
2. Check if the flag is equal to 0 and also maxValue is equal to 1, then return 0
3. Return maxValue.

解釋

我們給了 排列 of 整數。 我們已經要求找到給定數組中子數組可以容納的最大乘積。 該數組包含正數和負數。 我們只需要在這裡找到最大的產品。 我們在此使用的方法與子數組的最大長度(即最大和或最大乘積)相同。

現在,我們只需要專注於現在可以使用所有可能的子陣列獲得的最大乘積。 我們將關注最大範圍和最小範圍。 在maxValue中,我們將在此處存儲最大產品。 該標誌是用於檢查我們是否發現任何正數以及是否存在除1以外的最大乘積的變量。

我們將遍歷數組從0到n(其中n是數組的長度)。 我們將檢查arr [i]是否大於0。如果為true,則將maximumRange和arr [i]的乘積存儲到maximumRange中。 然後找出minimumRange與arr [i]與1的乘積之間的最小值,並將其存儲到minimumRange。

之後,還有另一個條件,如果子數組中的任何數組元素為0,則將minimumRange和maximumRange值標記為1。然後我們只需要從此處重新啟動即可。

如果不滿足任何條件。 然後找出minimumRange與arr [i]的乘積之間的最大值,並將其存儲到maximumRange。 maximumRange和arr [i]的乘積將存儲到minimumRange。 在每次遍歷時,我們都必須比較更大的值並將其更新為maxValue,最後返回maxValue,它將保存所有可能的子數組的最大乘積。

最大產品子陣列

推薦碼

CPP代碼以查找最大乘積子數組

#include<iostream>

using namespace std;

int maxSubarrayProduct(int arr[], int n)
{
    int maximumRange = 1;
    int minimumRange = 1;

    int maxValue = 1;
    int flag = 0;
    for (int i = 0; i < n; i++)
    {
        if (arr[i] > 0)
        {
            maximumRange = maximumRange * arr[i];
            minimumRange = min(minimumRange * arr[i], 1);
            flag = 1;
        }
        else if (arr[i] == 0)
        {
            maximumRange = 1;
            minimumRange = 1;
        }
        else
        {
            int temp = maximumRange;
            maximumRange = max(minimumRange * arr[i], 1);
            minimumRange = temp * arr[i];
        }
        if (maxValue < maximumRange)
            maxValue = maximumRange;
    }
    if (flag == 0 && maxValue == 1)
        return 0;
    return maxValue;
}
int main()
{
    int arr[] = { 2,-2,-3,-5};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum Sub array product is "<< maxSubarrayProduct(arr, n);
    return 0;
}
Maximum Sub array product is 15

Java代碼查找最大乘積子數組

class productSubarray
{
    public static int maxSubarrayProduct(int arr[])
    {
        int n = arr.length;
        int maximumRange = 1;
        int minimumRange = 1;

        int maxValue = 1;
        int flag = 0;
        for (int i = 0; i < n; i++)
        {
            if (arr[i] > 0)
            {
                maximumRange = maximumRange * arr[i];
                minimumRange = Math.min(minimumRange * arr[i], 1);
                flag = 1;
            }
            else if (arr[i] == 0)
            {
                maximumRange = 1;
                minimumRange = 1;
            }
            else
            {
                int temp = maximumRange;
                maximumRange = Math.max(minimumRange * arr[i], 1);
                minimumRange = temp * arr[i];
            }
            if (maxValue < maximumRange)
                maxValue = maximumRange;
        }
        if (flag == 0 && maxValue == 1)
            return 0;
        return maxValue;
    }
    public static void main(String[] args)
    {
        int arr[] = { 2,-2,-3,-5};
        System.out.println("Maximum Sub array product is "+ maxSubarrayProduct(arr));
    }
}
Maximum Sub array product is 15

複雜度分析

時間複雜度

O(N) 哪裡 “ n” 是數組中元素的數量。 因為我們對數組中的元素進行了循環。 該算法運行所需的總時間是線性的。

空間複雜度

O(1) 因為不需要額外的空間。 因為我們尚未存儲每個元素的數據。 取而代之的是,我們使用恆定的空間,因此空間複雜度是恆定的。