最大产品子阵列


难度级别 中等
经常问 亚马逊 思科 微软 摩根士丹利 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) 因为不需要额外的空间。 因为我们尚未存储每个元素的数据。 取而代之的是,我们使用恒定的空间,因此空间复杂度是恒定的。