程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 編程之美2.13——子數組的最大乘積

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

編輯：C++入門知識

問題：
給定一個長度為N的整數數組，只允許用乘法，不能用除法，計算任意(N-1)個數的組合中乘積最大的一組。

解法一：
采用空間換時間的策略，用兩個數組分別記錄原整數數組前綴與後綴的疊乘積（前綴s[i]=），再以間隔1個數的方式將這兩個數組乘起來就得到所有n-1個數的乘積數組（具體看代碼）。
[cpp]
#include <iostream>
#include <algorithm>
using namespace std;

#define MAXN 1003
long long A[MAXN];

long long s[MAXN];
long long t[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++)
        s[i] = s[i]*t[i+2];
    long long maximum = s[0];
    // 獲取其中的最大值
    for (i=1; i<=n-1; i++)
        maximum = max(maximum, s[i]);
    cout << maximum << endl;
}
解法二：
對N個數的乘積進行分析，用啟發式的方式得到在滿足乘積最大情況下要刪去那個數。
[cpp]
#include <iostream   >
#include <algorithm>
using namespace std;

#define MAXN 1003
long long A[MAXN];

#define INF 0x7fffffff

int main()
{
    int n, i, j;
    cin >> n;
    for (i=1; i<=n; i++)
        cin >> A[i];
    // 從前往後用疊乘法
    long long P = 1;
    for (i=1; i<=n; i++)
        P*=A[i];
    if (P==0)
    {
        for (j=1; j<=n && A[j]; j++);
        long long Q = 1;
        for (i=1; i<=n; i++)
            if (i!=j) Q *= A[i];
        if (Q>=0) cout << Q << "," << j << endl;
        else cout << "0" << endl;
    }
    else if (P>0)
    {
        for (i=1; i<=n && A[i]<0; i++);
        if (i<=n)
        {
            long long minPos = A[i];
            j = i;
            for (i=i+1; i<=n; i++)
                if (A[i]>0 && A[i]<minPos)
                {
                    minPos = A[i];
                    j = i;
                }
            long long Q = 1;
            for (i=1; i<=n; i++)
                if (i!=j) Q *= A[i];
            cout << Q << "," << j << endl;
        }
        else
        {
            long long minNeg = A[1];
            for (i=2; i<=n; i++)
                if (A[i] < minNeg)
                {
                    minNeg = A[i];
                    j = i;
                }
            long long Q = 1;
            for (i=1; i<=n; i++)
                if (i!=j) Q *= A[i];
            cout << Q << "," << j << endl;
        }
    }
    else
    {
        for (i=1; i<=n && A[i]>0; i++);
        long long maxNeg = A[i];
        j = i;
        for (i=i+1; i<=n; i++)
            if (A[i]<0 && A[i]>maxNeg)
            {
                maxNeg = A[i];
                j = i;
            }
        long long Q = 1;
        for (i=1; i<=n; i++)
            if (i!=j) Q *= A[i];
        cout << Q << "," << j << endl;
    }
}