乘积最大子数组

川长思鸟来 2023-02-09 13:24 24阅读 0赞

## 一、前言 ##

回顾前文[《最大子数组》][Link 1]，求解的是最高点到最低点差值，后经转换为累加和最大的子数组。对这个问题再扩展一下，将加给为乘，连续乘积最大的数组怎样求解呢？

《最大子数组》[https://blog.csdn.net/nie2314550441/article/details/106036517][Link 1]

## 二、题目 ##

给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

示例 1：

输入: \[2,3,-2,4\]

输出: 6

解释: 子数组 \[2,3\] 有最大乘积 6。

示例 2：

输入: \[-2,0,-1\]

输出: 0

解释: 结果不能为 2， 因为 \[-2,-1\] 不是子数组。

## 三、思路 ##

回顾一下《最大子数组——解法二》和 《包含min函数的栈》思路，从头到为遍历一次即可得到结果。想想能不能用这种思路解决这到题。整数有三种情况，正数、负数、零。零乘以然后数为零，零有分割重置的作用。我们只需要计算零之间的乘积即可。在两个0之间，负数可能有奇数个也可能有偶数个，只一次遍历我们无法判断后面负数个数，需要用2个数来辅助计算。一个数计算所有累乘结果，一个计算遇到第一个负数之后重置累乘结果。

(1) d1(n) = f(n) (f(n-1) = 0, 重置结果)

(2) d1(n) = d1(n-1) \* f(n);

(3) d2(n) = f(n) (f(n-1) = 0, 重置结果)

(4) d2(n) = f(n) (f(n-1) < 0, 且从上一个0到当前遇到第一个小于0的数）

(5) d2(n) = d2(n-1) \* f(n);

证明 max = max(d1(1..n), d2(1..n))

0可以重置后面的结果，我们只需要证明 max = max(d1(k..n), d2(k..n)) (k > 1 && f(k-1) = 0)

若 f(k...n) 有偶数个负数：

最大值为 d1(n) ，符合条件 d1(n) 包含在 d1(k..n) 或 d2(k...n) 中。

若 f(k...n) 有奇数个负数：

记负数坐标为：k1,k2...,kn 最大乘积为 max1 = f(k)\*f(k+1)\*...f(kn-1) 或

max2 = f(k1+1)\*f(k+1)\*...f(n)

max1 <=> d1(kn-1)

max2 <=> d(n) 在 (4)中第一次遇到负数会从后面开始累乘

max1，max2 包含在 d1(k..n) 或 d2(k...n) 中。

时间复杂度为 O(n)，空间复杂度 O(1)

### 四、编码实现 ###

两个解决方法，方法二为方法一的数学转换。

//==========================================================================
    /**
    * @file : 152_maxProduct.h
    * @tilte: 乘积最大子数组
    * @purpose : 给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
    *
    * 示例 1:
    *
    * 输入: [2,3,-2,4]
    * 输出: 6
    * 解释: 子数组 [2,3] 有最大乘积 6。
    * 示例 2:
    *
    * 输入: [-2,0,-1]
    * 输出: 0
    * 解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
    
    */
    //==========================================================================
    
    #pragma once
    #include <vector>
    #include <iostream>
    using namespace std;
    
    int maxProduct_solution_1(vector<int>& nums)
    {
    	if (nums.empty()) { return 0; }
    
    	int max = nums[0]; //最大乘积
    	int arr[2] = { nums[0] , nums[0] };		//遇到0，[0],[0]都重置; [0]: 从左往右累乘值; [1]: 从左往右累乘值若遇到第一个负数后面开始累乘; 
    	int minusCount = 0;
    	for (size_t i = 1; i < nums.size(); i++)
    	{
    		arr[0] *= nums[i];
    		arr[1] *= nums[i];
    		if (nums[i - 1] == 0)
    		{
    			// 遇到 0 就重置
    			arr[0] = nums[i];
    			arr[1] = nums[i];
    			minusCount = 0;
    		}
    		else if (nums[i - 1] < 0)
    		{
    			++minusCount;
    			if (minusCount == 1)
    			{
    				// 第一次遇到负数，后面数重新类似累乘
    				arr[1] = nums[i];
    			}
    		}
    
    		max = arr[0] > max ? arr[0] : max;
    		max = arr[1] > max ? arr[1] : max;
    	}
    
    	return max;
    }
    
    // 为 maxProduct_solution_1 数学模型转换
    int maxProduct_solution_2(vector<int>& nums)
    {
    	if (nums.empty()) { return 0; }
    
    	int max = nums[0]; //最大乘积
    	int arr[2] = { nums[0] , nums[0] };		//遇到0，[0],[0]都重置; [0]: 从左往右累乘值; [1]: 从左往右累乘值若遇到第一个负数后面开始累乘; 
    	for (size_t i = 1; i < nums.size(); i++)
    	{
    		arr[0] *= nums[i];
    		arr[1] *= nums[i];
    		if (nums[i - 1] == 0)
    		{
    			// 遇到 0 就重置
    			arr[0] = nums[i];
    			arr[1] = nums[i];
    		}
    		else if (nums[i - 1] < 0 && ((arr[0] > 0 && arr[1] > 0) || (arr[0] < 0 && arr[1] < 0)))
    		{
    			arr[1] = nums[i];
    		}
    
    		max = arr[0] > max ? arr[0] : max;
    		max = arr[1] > max ? arr[1] : max;
    	}
    
    	return max;
    }
    
    // 以下为测试代码
    #define NAMESPACE_MAXPRODUCT namespace NAME_MAXPRODUCT {
    #define NAMESPACE_MAXPRODUCTEND }
    
    //
    // 测试 用例 START
    NAMESPACE_MAXPRODUCT
    
    void test(const char* testName, vector<int>& data, int expect)
    {
    	int result1 = maxProduct_solution_1(data);
    	if (result1 == expect)
    	{
    		cout << testName << " solution_1 passed." << endl;
    	}
    	else
    	{
    		cout << testName << " solution_1 failed." << endl;
    	}
    
    	int result2 = maxProduct_solution_2(data);
    	if (result2 == expect)
    	{
    		cout << testName << " solution_2 passed." << endl;
    	}
    	else
    	{
    		cout << testName << " solution_2 failed." << endl;
    	}
    }
    
    // 测试用例
    void Test1()
    {
    	vector<int> data = { -1 };
    	int expect = -1;
    
    	test("Test1()", data, expect);
    }
    
    // 测试用例
    void Test2()
    {
    	vector<int> data = { 0 };
    	int expect = 0;
    
    	test("Test2()", data, expect);
    }
    
    // 测试用例
    void Test3()
    {
    	vector<int> data = { 10 };
    	int expect = 10;
    
    	test("Test3()", data, expect);
    }
    
    // 测试用例
    void Test4()
    {
    	vector<int> data = { 2, 3, 4 };
    	int expect = 24;
    
    	test("Test4()", data, expect);
    }
    
    // 测试用例
    void Test5()
    {
    	vector<int> data = { -2, -3, -4 };
    	int expect = 12;
    
    	test("Test5()", data, expect);
    }
    
    // 测试用例
    void Test6()
    {
    	vector<int> data = { -2, -4, -3 };
    	int expect = 12;
    
    	test("Test6()", data, expect);
    }
    
    // 测试用例
    void Test7()
    {
    	vector<int> data = { 1, -2, -4, -3 };
    	int expect = 12;
    
    	test("Test7()", data, expect);
    }
    
    // 测试用例
    void Test8()
    {
    	vector<int> data = { -2, -4, 1, -3 };
    	int expect = 12;
    
    	test("Test8()", data, expect);
    }
    
    // 测试用例
    void Test9()
    {
    	vector<int> data = { 2, 3 ,-1, 4, 2 };
    	int expect = 8;
    
    	test("Test9()", data, expect);
    }
    
    // 测试用例
    void Test10()
    {
    	vector<int> data = { 2, 3, -1, 4, 2, -2 };
    	int expect = 96;
    
    	test("Test10()", data, expect);
    }
    
    // 测试用例
    void Test11()
    {
    	vector<int> data = { 2, 3, -1, 0, 2, -2 };
    	int expect = 6;
    
    	test("Test11()", data, expect);
    }
    
    // 测试用例
    void Test12()
    {
    	vector<int> data = { 2, 3, -2, 2, 4, -1, 6 };
    	int expect = 576;
    
    	test("Test12()", data, expect);
    }
    
    // 测试用例
    void Test13()
    {
    	vector<int> data = { 2, 3, -2, 2, 0, -1, 6, 0, 10 };
    	int expect = 10;
    
    	test("Test13()", data, expect);
    }
    
    // 测试用例
    void Test14()
    {
    	vector<int> data = { 15, 0, 2, 3, -2, 2, 0, -1, 6, 0, 10 };
    	int expect = 15;
    
    	test("Test14()", data, expect);
    }
    
    // 测试用例
    void Test15()
    {
    	vector<int> data = { 15, 0, 2, 3, -2, -2, 0, -1, 6, 0, 10 };
    	int expect = 24;
    
    	test("Test15()", data, expect);
    }
    
    // 测试用例
    void Test16()
    {
    	vector<int> data = { 15, 0, 2, 3, -2, -2, 0, -1, 6, -3, 10 };
    	int expect = 180;
    
    	test("Test16()", data, expect);
    }
    
    NAMESPACE_MAXPRODUCTEND
    // 测试 用例 END
    //
    
    void MaxProduct_Test()
    {
    	NAME_MAXPRODUCT::Test1();
    	NAME_MAXPRODUCT::Test2();
    	NAME_MAXPRODUCT::Test3();
    	NAME_MAXPRODUCT::Test4();
    	NAME_MAXPRODUCT::Test5();
    	NAME_MAXPRODUCT::Test6();
    	NAME_MAXPRODUCT::Test8();
    	NAME_MAXPRODUCT::Test9();
    	NAME_MAXPRODUCT::Test10();
    	NAME_MAXPRODUCT::Test11();
    	NAME_MAXPRODUCT::Test12();
    	NAME_MAXPRODUCT::Test13();
    	NAME_MAXPRODUCT::Test14();
    	NAME_MAXPRODUCT::Test15();
    	NAME_MAXPRODUCT::Test16();
    }

**执行结果：**

![20200519084603571.png][]

[Link 1]: https://blog.csdn.net/nie2314550441/article/details/106036517
[20200519084603571.png]: https://img-blog.csdnimg.cn/20200519084603571.png