C++程序寻找最大积子数组

给定一个包含正数和负数的数组，找到最大积子数组的积。预期时间复杂度为O(n)，只能使用O(1)的额外空间。

示例：

输入：arr[]={6, -3, -10, 0, 2}
输出：180 //最大子数组分别为{6, -3, -10}

输入：arr[]={-1, -3, -10, 0, 60}
输出：60 //最大子数组分别为{60}

输入：arr[]={-2, -40, 0, -2, -3}
输出：80 //最大子数组分别为{-2, -40}

Naive解法：

思想是遍历每个连续的子数组，找到每个子数组的积，并从这些结果中返回最大积。

下面是上述方法的实现。

// C++ program to find Maximum Product Subarray
#include <bits/stdc++.h>
using namespace std;
 
/* 返回最大积子数组的积。*/
int maxSubarrayProduct(int arr[], int n)
{
    // 初始化结果
    int result = arr[0];
 
    for (int i = 0; i < n; i++)
    {
        int mul = arr[i];
        // 遍历当前子数组
        for (int j = i + 1; j < n; j++)
        {
            // 每次更新结果
            // 以便监视最大积
            result = max(result, mul);
            mul *= arr[j];
        }
        // 更新最后一个元素的结果。
        result = max(result, mul);
    }
    return result;
}
 
// 主函数
int main()
{
    int arr[] = { 1, -2, -3, 0, 7, -8, -2 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "最大子数组积是："
         << maxSubarrayProduct(arr, n);
    return 0;
}
 
// 由yashbeersingh42提供的代码```

输出结果：

最大子数组积是：112

时间复杂度： O(N 2 )

辅助空间： O(1)

高效解法：

以下解法假设给定的输入数组总有一个正的输出。该解法适用于上述所有情况。但不适用于数组，例如 {0, 0, -20, 0}、{0，0，0} 等。该解决方案可以很容易地修改以处理此问题。
它类似于最大总和连续子数组问题。这里唯一需要注意的是，最大积也可以通过前一个元素的最小（负）积乘以此元素获得。例如，在数组 {12, 2, -3, -5, -6, -2} 中，当我们位于元素 -2 时，最大积是最小积，它以 -6 结尾并乘以 -2。

// C++ 程序，用于查找最大乘积子数组
#include <bits/stdc++.h>
using namespace std;
 
/* 返回最大乘积子数组的乘积。
假设给定的数组总是有一个乘积大于1的子数组 */
int maxSubarrayProduct(int arr[], int n)
{
    // 最大正结束位置的乘积
    int max_ending_here = 1;
 
    // 最小负结束位置的乘积
    int min_ending_here = 1;
 
    // 初始化总体最大产品
    int max_so_far = 0;
    int flag = 0;
    /* 遍历数组。
    i次迭代后，保留以下值：
    max_ending_here始终为1，或以arr[i]结尾的一些正数乘积
    min_ending_here始终为1，或以arr[i]结尾的某些负数乘积 */
    for (int i = 0; i < n; i++)
    {
        /* 如果这个元素是正数，请更新max_ending_here。仅在min_ending_here为负数时更新min_ending_here */
        if (arr[i] > 0)
        {
            max_ending_here = max_ending_here * arr[i];
            min_ending_here
                = min(min_ending_here * arr[i], 1);
            flag = 1;
        }
 
        /* 如果这个元素是0，则最大乘积无法在这里结束，请将max_ending_here和min_ending_here都设置为0。
        假设：输出始终大于或等于1。 */
        else if (arr[i] == 0) {
            max_ending_here = 1;
            min_ending_here = 1;
        }
 
        /* 如果这个元素是负数。 这是棘手的，可以使max_ending_here为1或正数。
         min_ending_here可以为1或负数。
         next max_ending_here将始终是prev。
         min_ending_here * arr[i]，如果prev max_ending_here为1，则next min_ending_here为1，否则
         next min_ending_here将是prev max_ending_here * arr[i] */
 
        else {
            int temp = max_ending_here;
            max_ending_here
                = max(min_ending_here * arr[i], 1);
            min_ending_here = temp * arr[i];
        }
 
        // 如果需要，则更新max_so_far
        if (max_so_far < max_ending_here)
            max_so_far = max_ending_here;
    }
    if (flag == 0 && max_so_far == 0)
        return 0;
    return max_so_far;
}
 
// 驱动器代码
int main()
{
    int arr[] = { 1, -2, -3, 0, 7, -8, -2 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "最大子数组乘积是 "
         << maxSubarrayProduct(arr, n);
    return 0;
}
 
// 本代码由rathbhupendra捐赠```

输出