# 最大產品子陣列

## 例

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

## 算法

```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.```

## 推薦碼

### 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） 因為不需要額外的空間。 因為我們尚未存儲每個元素的數據。 取而代之的是，我們使用恆定的空間，因此空間複雜度是恆定的。