編程之美2.13子數組的最大乘積

題目：

給定一個長度為N的數組，只許用乘法，不許用除法，計算任意（N-1）個數的組合中乘積最大的一個組，并寫出算法的時間復雜度。

如果把所可能的乘積找出來，共有（N-1）個數，n個n-1的數的組合，時間復雜度為O（N^2）。

解法一：

在一個數組中，以i為界限，分別計算i前面s[i-1]的積，后面t[i+1]的積

p[i]=s[i-1]*t[i+1]即為這個數組中除去i的所有數的乘積。

時間復雜度為，從頭到尾和從尾到頭遍歷數組得到s[]和t[]的時間，加上p[]的時間3N,加上查找最大值的時間復雜度，最后總得時間復雜度為O(n)。

注意在代碼編寫的過程中，因為若干個數的乘積較大，需要把數組定義為longlong型。

#include <iostream>
#include <algorithm>
using namespace std;

#define MAXN 1000

long long A[MAXN];
long long s[MAXN];
long long t[MAXN];
long long p[MAXN];

int main()
{
    int n, i;
    cin >> n;
    for (i=1; i<=n; i++)
        cin >> A[i];
    // 從前往后用疊乘法
    s[0] = 1;
    for (i=1; i<n; i++)
        s[i]=A[i]*s[i-1];
    // 從后往前用疊乘法
    t[n+1] = 1;
    for (i=n; i>1; i--)
        t[i]=A[i]*t[i+1];
    // 計算出n-1個n-1數連乘
    for (i=0; i<=n-1; i++)
        p[i] = s[i]*t[i+2];
    long long maximum = p[0];
    // 獲取其中的最大值
    for (i=1; i<=n-1; i++)
        maximum = max(maximum, p[i]);
    cout <<"max is "<< maximum << endl;
}

?

解法二

近一步分析，假設N個整數的乘積為P，從P的正負性下手。

1.P=0；數組中至少含一個0。除去一個0，其他N-1個數的乘積為Q

　　Q=0；數組中至少2個0；所以N-1的乘積依然為0；

　　Q>0；用0替換N-1中的任意一個數，得出的Pn-1=0，所以最大值為Q；

　　Q<0；用0替換N-1中的任意數，Pn-1=0，最大值為0；

2.P<0

　　如果去除數組中的一個負數，剩下的n-1個數的乘積為正，去掉絕對值最小的負數得到的n-1個數最大。

3.P>0

　　去掉數組匯總最小的正數值，如果沒有正數都是負數，取出絕對值最大的負數值。

?

判斷正負的過程，一般不使用所有數據直接相乘的操作，因為數據的值可能過大，有溢出的危險，所以可以通過判斷數組中，正數，負數，零的個數。遍歷一次數組，即可得到這些數據，還有絕對值最大最小的正負數。時間復雜度為O(N)。