本文主要是介绍2.13 子数组的最大乘积，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：
给定一个长度为N的整形数组，只允许用乘法，不能用除法。计算任意N-1个数的组合中乘积最大的一组。
方法一：
#include <iostream>#define MAXN 10000using namespace std;int n, a[MAXN], s[MAXN], t[MAXN], p[MAXN];//s[i]表示数组前i个元素的乘积
//t[i]表示数组后N-i个元素的乘积
//p[i] = s[i-1] * t[i+1];
//p[i]表示数组除第I个元素外，其他N-1个元素的乘积
//s[i]=A[0]*A[1]*…A[i], t[i]=A[i]*A[i+1]*…A[N-1]
//则p[i] = s[i-1] * t[i+1]。int main() {cin >> n;for(int i = 0; i < n; ++i) cin >> a[i];int sv = 1, tv = 1;for(int i = 0; i < n; ++i) {int j = n-i-1;sv *= a[i];tv *= a[j];s[i] = sv;t[j] = tv;}int maxNum = p[0] = t[1]; //p[0]和t[1]表示除了最前面那个元素,剩下的N-1个元素相乘的值。for(int i = 1; i < n; ++i) {p[i] = s[i-1] * t[i+1];maxNum = maxNum < p[i] ? p[i] : maxNum;}cout << maxNum << endl;return 0;
}
方法二：
思路：
子数组最大乘积问题可以分为以下几种情况。
1.数组中有多于一个零则最大乘积为0；
2.数组中只有一个零，而有奇数个负数，则最大乘积必定为0；
3.数组中只有一个零，而有偶数个负数，则最大乘积为除去0的元素的乘积；
4.数组中没有零，而有奇数个负数，则最大乘积为除去绝对值最小的负数的乘积；
5.数组中没有零，而有偶数个负数，则最大乘积为除去最小的正数的乘积。
所以求出数组中正数的个数，负数的个数，以及0的个数！这样就是最简单的方法了！
这篇关于2.13 子数组的最大乘积的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
