实现子数组的最大乘积

时间：2010-12-06 来源：liangdiamond

问题描述：

给定一个长度为N的整数数组，只允许用乘法，不能用除法，计算任意(N-1)个数的组合乘积中的最大的一组。

算法描述：

设array为初始数组，s[i]表示数组前i个元素的乘积s[i]=s[i-1]*array[i-1].t[i]表示数组后(N-i)个元素的乘积t[i]=t[i+1]*array[i+1]

设p[i]为数组除第i个元素外，其它N-1个元素的乘积，即有：

p[i]=s[i-1]*t[i+1]

求出p[i]的最大值，即该题目的解

写测试用例：(测试用例框架用的是google的GTest)

对测试case进行初始化：

代码

测试数组的初始化：

TEST_F(CCalcTest,InitRight)
{
    int* ptrArray = m_calc->GetPtrArray();
    for(int i=0;i<10;i++)
    {
        EXPECT_GE(10,ptrArray[i]);
        EXPECT_LE(1,ptrArray[i]);
    }
}

测试获取s[i]

代码 TEST_F(CCalcTest,CalcBeginSubArray)
{
    int array1[1] = {2};
    m_calc->CalcBeginSubArray(array1,sizeof(array1)/sizeof(int));
    EXPECT_EQ(1,(m_calc->GetBeginPtrArray())[0]);

    int array2[4] = {3,2,3,4};
    m_calc->CalcBeginSubArray(array2,sizeof(array2)/sizeof(int));
    EXPECT_EQ(1,(m_calc->GetBeginPtrArray())[0]);
    EXPECT_EQ(3,(m_calc->GetBeginPtrArray())[1]);
    EXPECT_EQ(6,(m_calc->GetBeginPtrArray())[2]);
    EXPECT_EQ(18,(m_calc->GetBeginPtrArray())[3]);
}

测试获取t[i]

代码 TEST_F(CCalcTest,CalcBehindSubArray)
{
    int array1[1] = {2};
    m_calc->CalcBehindSubArray(array1,sizeof(array1)/sizeof(int));
    EXPECT_EQ(1,(m_calc->GetBehindPtrArray())[0]);

    int array2[4] = {2,2,3,4};
    m_calc->CalcBehindSubArray(array2,sizeof(array2)/sizeof(int));
    EXPECT_EQ(24,(m_calc->GetBehindPtrArray())[0]);
    EXPECT_EQ(12,(m_calc->GetBehindPtrArray())[1]);
    EXPECT_EQ(4,(m_calc->GetBehindPtrArray())[2]);
    EXPECT_EQ(1,(m_calc->GetBehindPtrArray())[3]);
}

测试获取p[i]

代码 TEST_F(CCalcTest,CalcArrayMul)
{
    int array[4] = {2,2,3,4};
    m_calc->Init(array,4);
    m_calc->CalcArrayMul();
    EXPECT_EQ(24,(m_calc->GetAnsArray())[0]);
    EXPECT_EQ(24,(m_calc->GetAnsArray())[1]);
    EXPECT_EQ(16,(m_calc->GetAnsArray())[2]);
    EXPECT_EQ(12,(m_calc->GetAnsArray())[3]);
}

测试获取数组最大值

TEST_F(CCalcTest, CalcMaxFromArray)
{
int array[4] = {2,2,3,4};
EXPECT_EQ(4,m_calc->CalcMaxFromArray(array, 4));
}

整合到一起测试

代码 TEST_F(CCalcTest,CalcALL)
{
    int array1[4] = {2,2,3,4};
    m_calc->Init(array1,4);
    m_calc->CalcArrayMul();
    EXPECT_EQ(24,m_calc->CalcMaxFromArray(m_calc->GetAnsArray(), 4));

    int array2[6] = {1,-1,2,2,3,4};
    m_calc->Init(array2,6);
    m_calc->CalcArrayMul();
    EXPECT_EQ(48,m_calc->CalcMaxFromArray(m_calc->GetAnsArray(), 6));
}

所有程序代码：

#ifndef CALC_H #define CALC_H class CCalc { private: //数组的首地址 int* m_pArray; //数组的长度 int m_length; int* m_pBeginArray; int* m_pBehindArray; int* m_pCalcArray; public: CCalc(); CCalc(int size); ~CCalc(); //初始化数组 void Init(); void Init(int* pArray, int length); //返回数组的首地址 int* GetPtrArray() const; //返回数组前n个元素的乘积s[i]首地址 int* GetBeginPtrArray() const; //返回数组后n个元素的乘积t[i]首地址 int* GetBehindPtrArray() const; //返回结果数组 int* GetAnsArray() const; //返回数组的长度 int GetArrayLength() const; //计算s[i] int CalcBeginSubArray(int* pArray,int length); //计算t[i] int CalcBehindSubArray(int* pArray,int length); //计算p[i] void CalcArrayMul(); //获取数组的最大值 int CalcMaxFromArray(int* pArray, int length); }; #endif