[经典面试题]子数组的最大乘积

题目

给定一个长度为N的整数数组,只允许用乘法,不能用除法,计算任意(N-1)个数的组合乘积中的最大的一组,并写出算法的时间复杂度。

思路一 穷举法

我们把所有可能的(N-1)个数的组合找出来,分别计算它们的乘积,并比较大小。由于总共有N个(N-1)个数的组合,总的时间复杂度为O(N^2),但显然这不是最好的思路。

思路二 空间换时间

计算(N-1)个数的组合乘积,假设第i个(0<=i<=N-1)元素被排除在乘积之外(如下图)。

设num[]为初试数组
Left[i]表示前i个元素(包括第i个元素)的乘积(0<=i<=N-1)
Left[i] = Left[i-1] * num[i]
Right[i]表示后N-i个元素(包括第i个元素)的乘积(0<=i<=N-1)
Right[i] = Right[i+1] * num[i]

设p[i]为数组除第i个元素外,其他N-1个元素的乘积:
P[i] = Left[i-1] * Right[i+1]

举个例子:

P[4] = Left[3] * Right[5]
= a1 * a2 * a3 * a4 * a6 * a7 * a8 * a9 * a10

由于只需要从头到尾,从尾到头扫描两次即可得到数组Left[] 和 Right[],从而线性时间得到P[i]。所以很容易的就可以得到最大值(只需遍历一次p数组)。总的时间复杂度为计算数组Left[],Right[],p[]的时间复杂度加上查找p[]最大值的时间复杂度即O(N)。

代码一

  /*---------------------------------------------
    *   日期:2015-02-15
    *   作者:SJF0115
    *   题目: 子数组的最大乘积
    *   来源:
    *   博客:
    -----------------------------------------------*/
    #include <iostream>
    #include <cstring>
    using namespace std;

    class Solution {
    public:
        double MaxProduct(double num[],int n){
            if(n <= 0){
                return 0;
            }//if
            double max = num[0],p;
            double Left[n],Right[n];
            // 初始化
            Left[0] = num[0];
            Right[n-1] = num[n-1];
            // 计算Left数组
            for(int i = 1;i < n;++i){
                Left[i] = Left[i-1] * num[i];
            }//for
            // 计算Right数组
            for(int i = n-2;i >= 0;--i){
                Right[i] = Right[i+1] * num[i];
            }//for
            // max
            int left,right;
            for(int i = 0;i < n;++i){
                left = (i - 1) >= 0 ? Left[i-1] : 1;
                right = (i + 1) < n ? Right[i+1] : 1;
                p = left * right;
                if(p > max){
                    max = p;
                }//if
            }//for
            return max;
        }
    };

    int main() {
        Solution solution;
        double num[] = {-2.5,-4,0.5,3,1,2,-3};
        cout<<solution.MaxProduct(num,7)<<endl;
    }

思路二

通过分析,进一步减少计算量。假设N个数的乘积为P,针对P的正负性进行如下分析:
(1)P为0
那么,数组中至少包含一个0。假设除去一个0之外,其他N-1个数的乘积为Q,根据Q的正负性进行讨论:
Q为0,说明数组中至少有两个0,那么N-1个数的乘积只能为0。
Q为正,返回Q。因为如果用0替换剩余N-1个数中的任意一个,所得乘积结果都为0,小于之前的Q,因此乘积最大值为Q。
Q为负,返回0。因为如果用0替换剩余N-1个数中的任意一个,所得结乘积果都为0,大于之前的Q,因此乘积最大值为0。
(2)P为负
根据“负负得正”的乘法性质,自然想到的是从N个整数中去掉一个负数,使得N-1个数乘积为正数。而要使这个整数最大,这个被去掉的负数绝对值必须是数组中最小的。我们只需要扫描一遍数组,把绝对值最小的负数去掉就可以了。
(3)P为正
类似P为负的情况,应该去掉一个绝对值最小的正数值,这样得到的N-1个数乘积就是最大的。

上面的思路采用了直接求N个数的乘积P,进而判断P的正负性的办法,但是直接求乘积往往有溢出的危险,事实上可做一个小的转变,不需要直接乘积,而是求出数组中正数,负数和0的个数,从而判断P的正负性。

在时间复杂度上,由于只需要一次遍历数组,在遍历数组的同时就可得到数组中正数,负数和0的个数,以及数组中绝对值最小的正数和负数,时间复杂度为O(N)

代码二

    /*---------------------------------------------
    *   日期:2015-02-15
    *   作者:SJF0115
    *   题目: 子数组的最大乘积
    *   来源:
    *   博客:
    -----------------------------------------------*/
    #include <iostream>
    #include <climits>
    #include <cmath>
    using namespace std;

    class Solution {
    public:
        double MaxProduct(double num[],int n){
            if(n <= 0){
                return 0;
            }//if
            // 绝对值最小的负数,绝对值最小的正数
            double pMin = INT_MAX,nMin = INT_MAX;
            // 绝对值最小的负数,绝对值最小的正数,0的下标
            int pIndex = 0,nIndex = 0,zeroIndex;
            // 0,正数,负数个数
            int zCount = 0,pCount = 0,nCount = 0;
            // 去除掉元素的下标
            int index = 0;
            // 统计
            for(int i = 0;i < n;++i){
                if(num[i] == 0){
                    zeroIndex = i;
                    ++zCount;
                }//if
                else if(num[i] > 0){
                    ++pCount;
                    // 绝对值最小的正数
                    if(num[i] < pMin){
                        pIndex = i;
                        pMin = num[i];
                    }//if
                }//else
                else{
                    ++nCount;
                    // 绝对值最小的负数
                    if(fabs(num[i]) < nMin){
                        nMin = fabs(num[i]);
                        nIndex = i;
                    }//if
                }//else
            }//for
            // P为0
            if(zCount > 0){
                // Q为0
                if(zCount - 1 > 0){
                    return 0;
                }//if
                // Q为负
                if(nCount % 2){
                    return 0;
                }//if
                // Q为正
                else{
                    // 去掉下标为zeroIndex的元素
                    index = zeroIndex;
                }//else
            }//if
            // P为正去掉绝对值最小的正数
            else if(nCount % 2 == 0){
                index = pIndex;
            }
            // P为负去掉绝对值最小的负数
            else{
                index = nIndex;
            }//else
            // 最大乘积
            double max = 1;
            for(int i = 0;i < n;++i){
                if(i != index){
                    max *= num[i];
                }//if
            }//for
            return max;
        }
    };

    int main() {
        Solution solution;
        double num[] = {2.5,4,-0.5,3,-1,2,3};
        cout<<solution.MaxProduct(num,7)<<endl;
    }

相似题目

[经典面试题]最大连续乘积

时间: 2024-11-03 04:10:09

[经典面试题]子数组的最大乘积的相关文章

[经典面试题]最大连续乘积

题目 给一个浮点数序列,取最大乘积连续子串的值,例如 -2.5,4,0,3,0.5,8,-1,则取出的最大乘积连续子串为3,0.5,8.也就是说,上述数组中,3 0.5 8这3个数的乘积3*0.5*8=12是最大的,而且是连续的. 分析 最大乘积连续子串与最大乘积子序列不同,前者子串要求连续,后者子序列不要求连续.初看此题,自然会想到最大连续乘积问题类似于最大子数组和问题 思路一 穷举法 穷举子串的起点和终点. 代码一 /*------------------------------------

[LeetCode] Subarray Product Less Than K 子数组乘积小于K

Your are given an array of positive integers nums. Count and print the number of (contiguous) subarrays where the product of all the elements in the subarray is less than k. Example 1: Input: nums = [10, 5, 2, 6], k = 100 Output: 8 Explanation: The 8

[经典面试题]在O(1)时间删除链表结点

[题目] 给定链表的头指针和一个结点指针,在O(1)时间删除该结点.链表结点的定义如下: struct ListNode {     int        value;     struct ListNode*  next; }; 函数的声明如下: void DeleteNode(ListNode* head,ListNode* node); [思路] 这是一道广为流传的Google面试题,能有效考察我们的编程基本功,还能考察我们的反应速度,更重要的是,还能考察我们对时间复杂度的理解. 在链表中

[经典面试题]将字符串里的小写字母转换成大写的。 要求不通过比较

[题目] 将字符串里的小写字母转换成大写的. 要求不通过比较 --------腾讯校招 [思路] a~z的ascii码:97~122 也就是:1100001~1111010 A~Z的ascii码:65~90 也就是: 1000001~1011010 通过判断从低位数第五位是否是0,1而得到是小写字母还是大写字母 [代码] /********************************* * 日期:2014-11-21 * 作者:SJF0115 * 题目: 将字符串里的小写字母转换成大写的.

PHP经典面试题集锦

 这篇文章主要介绍了PHP经典面试题集锦,搜集整理了常见的php面试题与相关的参考答案,供大家参考借鉴,需要的朋友可以参考下     本文较为详细的分析了PHP经典面试题.分享给大家供大家参考.具体如下: 做了一下网络上的php题目,不知不觉做到现在.....把答案贴出来,供参考之用. 1.用PHP打印出前一天的时间格式是2006-5-10 22:21:21(2分) ? 1 2 $a = date("Y-m-d H:i:s", strtotime("-1 day")

nosql-mongodb对象的子数组计算相关疑问

问题描述 mongodb对象的子数组计算相关疑问 结构:{ name:"张三",sex:"男",scroe:[{lesson:"物理",total:60},{lesson:"化学",total:72}], name:"李四",sex:"女",scroe:[{lesson:"物理",total:92},{lesson:"数学",total:81}]

[经典面试题]输入一个排好序的数组的一个旋转,输出旋转数组的最小元素。

[题目] 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转.输入一个排好序的数组的一个旋转,输出旋转数组的最小元素.例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转,该数组的最小值为1. [分析] 这道题最直观的解法并不难.从头到尾遍历数组一次,就能找出最小的元素,时间复杂度显然是O(N).但这个思路没有利用输入数组的特性,我们应该能找到更好的解法.  我们注意到旋转之后的数组实际上可以划分为两个排序的子数组,而且前面的子数组的元素都大于或者等于后

[经典面试题]二分查找问题汇总

[算法]二分查找算法 1.[给定一个有序(非降序)数组A,可含有重复元素,求最小的i使得A[i]等于target,不存在则返回-1.] [题目] 给定一个有序(非降序)数组A,可含有重复元素,求最小的i使得A[i]等于target,不存在则返回-1. [分析] 此题也就是求target在数组中第一次出现的位置.这里可能会有人想先直接用原始的二分查找,如果不存在直接返回-1, 如果存在,然后再顺序找到这个等于target值区间的最左位置,这样的话,最坏情况下的复杂度就是O(n)了,没有完全发挥出二

[华为机试练习题]56.求子数组的最大和

题目 描述: 输入一个整形数组.数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和.求所有子数组的和的最大值. 接口 Int GetSubArraySum(Int* pIntArray,Int nCount): 规格 要求时间复杂度为O(n) 举例 例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5,和最大的子数组为3, 10, -4, 7, 2, 因此输出为该子数组的和18 练习阶段: 初级 代码 /*-------------------------------