数据结构-乘积最小的连续子数组

爱被打了一巴掌 2022-05-19 09:40 185阅读 0赞

找到数组 nums\[ \]中乘积最小的连续子数组,输出该乘积。 数组中的数据包含正数,负数。

**要求时间复杂度：O（n）**

![640_wx_fmt_png_tp_webp_wxfrom_5_wx_lazy_1][]

#include<iostream>
    #include<cstdlib> 
    #include<cstring>
    #include<cmath>
    #define MAX 0x3f3f3f3f
    #define MIN 0xc0c0c0c0
    using namespace std;
    
    int MinProductSubArray(int data[], int n)
    {
    	/*
    		当走到某一个元素时，简单考虑，只包含两种情况
    		1.如果要包含当前元素，则最小值是当前值和前面算好的最大值或则最小值乘积中最小的一个（因为有正有负 ）
    		2.如果不包含当前元素，则证明要断开了。最小值肯定是自身了 
    		
    		所以只要算出当前元素与（当前元素*之前最大值）与（当前元素*之前最小值）中最小的即可！ 
    		
    		根据如上分析，还要计算每一步的最大值，因为计算最小值的时候要用到，那么和计算最小值的考虑是相同的
    		1.如果要包含当前元素，则最大值是当前值和前面算好的最大值或则最小值乘积中最大的一个（因为有正有负 ）
    		2.如果不包含当前元素，则证明要断开了。最大值肯定是自身了 
    		
    		所以只要算出当前元素与（当前元素*之前最大值）与（当前元素*之前最小值）中最大的即可！ 
    	*/
    	int max, min, result, tmp;
    	max = data[0];
    	min = data[0];
    	result = data[0];
    	for(int i = 1; i < n; i++)
    	{
    		tmp = max;
    		max = data[i] * max > data[i] * min ? data[i] * max : data[i] * min;
    		max = max > data[i] ? max : data[i];
    		
    		min = data[i] * tmp > data[i] * min ? data[i] * min : data[i] * tmp;
    		min = min < data[i] ? min : data[i];
    		if(min < result)
    			result = min;
    	}
    	return result;
    }
    
    int main()
    {
    
    	int data[] = {2, -3, -2, 4};
    	int minNum = MinProductSubArray(data, 4);
    	cout<<"The Min Product is:"<<minNum<<endl;
    }

[640_wx_fmt_png_tp_webp_wxfrom_5_wx_lazy_1]: /images/20220519/7e5aec16f30b4390a27374d43d66406f.png