Skip to content

Latest commit

 

History

History
203 lines (158 loc) · 9.31 KB

05.02.md

File metadata and controls

203 lines (158 loc) · 9.31 KB
Raw

第二十八章：最大连续乘积子串

前言

这一章和下一章的问题皆是各大IT公司最喜欢出的笔试面试题之一，比如说前者是小米2013年校招笔试原题，而后者则更是反复出现，如去年9月26日百度一二面试题，10月9日腾讯面试题第1小题，10月13日百度2013校招北京站笔试题第二 大道题第3小题，及去年10月15日2013年Google校招笔试最后一道大题皆是考察下一章的字符串编辑距离问题。

题目描述：

给一个浮点数序列，取最大乘积连续子串的值，例如 -2.5，4，0，3，0.5，8，-1，则取出的最大乘积连续子串为3，0.5，8。也就是说，上述数组中，3 0.5 8这3个数的乘积30.58=12是最大的，而且是连续的。

提醒：此最大乘积连续子串与最大乘积子序列不同，请勿混淆，前者子串要求连续，后者子序列不要求连续。也就是说：最长公共子串（Longest CommonSubstring）和最长公共子序列（LongestCommon Subsequence，LCS）的区别：

  • 子串（Substring）是串的一个连续的部分，

  • 子序列（Subsequence）则是从不改变序列的顺序，而从序列中去掉任意的元素而获得的新序列；

更简略地说，前者（子串）的字符的位置必须连续，后者（子序列LCS）则不必。比如字符串“ acdfg ”同“ akdfc ”的最长公共子串为“ df ”，而它们的最长公共子序列LCS是“ adf ”，LCS可以使用动态规划法解决。

解答：

解法一、 穷举，所有的计算组合：

或许，读者初看此题，自然会想到最大乘积子序列问题类似于最大子数组和问题，可能立马会想到用最简单粗暴的方式：两个for循环直接轮询。

double max = 0;
double start = 0;
double end = 0;
for (int i = 0; i < num; i++)
{
    double x = arrs[i];
    for (int j = i + 1; j < num; j++)
    {
        x *= arrs[j];
        if (x > max)
        {
            max = x;
            start = arrs[i];
            end = arrs[j];
        }
    }
}

解法二、 虽说类似于最大子数组和问题，但实际上具体处理起来诸多不同。为什么呢，因为乘积子序列中有正有负也还可能有0。我们可以把问题简化成这样：数组中找一个子序列，使得它的乘积最大；同时找一个子序列，使得它的乘积最小（负数的情况）。因为虽然我们只要一个最大积，但由于负数的存在，我们同时找这两个乘积做起来反而方便。也就是说，不但记录最大乘积，也要记录最小乘积。So，我们让

  • maxCurrent表示当前最大乘积的candidate，
  • minCurrent反之，表示当前最小乘积的candidate，
  • 而maxProduct则记录到目前为止所有最大乘积candidates的最大值。 （以上用candidate这个词是因为只是可能成为新一轮的最大/最小乘积）

由于空集的乘积定义为1，在搜索数组前，maxCurrent，minCurrent，maxProduct都赋为1。 假设在任何时刻你已经有了maxCurrent和minCurrent这两个最大/最小乘积的candidates，新读入数组的元素x(i)后，新的最大乘积candidate只可能是maxCurrent或者minCurrent与x(i)的乘积中的较大者，如果x(i) < 0导致maxCurrent < minCurrent，需要交换这两个candidates的值。

当任何时候maxCurrent<1，由于1（空集）是比maxCurrent更好的candidate，所以更新maxCurrent为1，类似的可以更新minCurrent。任何时候maxCurrent如果比最好的maxProduct大，更新maxProduct。

代码一：

template <typename Comparable>
Comparable maxprod( const vector<Comparable>&v)
{
    int i;
    Comparable maxProduct = 1;
    Comparable minProduct = 1;
    Comparable maxCurrent = 1;
    Comparable minCurrent = 1;
    //Comparable t;

    for ( i = 0; i < v.size() ; i++)
    {
        maxCurrent *= v[i];
        minCurrent *= v[i];
        if (maxCurrent > maxProduct)
            maxProduct = maxCurrent;
        if (minCurrent > maxProduct)
            maxProduct = minCurrent;
        if (maxCurrent < minProduct)
            minProduct = maxCurrent;
        if (minCurrent < minProduct)
            minProduct = minCurrent;
        if (minCurrent > maxCurrent)
            swap(maxCurrent, minCurrent);
        if (maxCurrent < 1)
            maxCurrent = 1;
        //if(minCurrent>1)
        //    minCurrent =1;
    }
    return maxProduct;
}

解法三、 本题除了上述类似最大子数组和的解法，也可以直接用动态规划求解（其实，上述的解法一本质上也是动态规划，只是解题所表现出来的具体形式与接下来的解法二不同罢了。这个不同就在于下面的解法二会写出动态规划问题中经典常见的DP方程，而解法一是直接求解）。具体解法如下：

假设数组为a[]，直接利用动归来求解，考虑到可能存在负数的情况，我们用Max来表示以a结尾的最大连续子串的乘积值，用Min表示以a结尾的最小的子串的乘积值，那么状态转移方程为：

  Max=max{a, Max[i-1]*a, Min[i-1]*a};  
  Min=min{a, Max[i-1]*a, Min[i-1]*a};

初始状态为Max[1]=Min[1]=a[1]。

C/C++代码一：

double func(double *a, const int n)
{
    double *maxA = new double[n];
    double *minA = new double[n];
    maxA[0] = minA[0] = a[0];
    double value = maxA[0];
    for (int i = 1 ; i < n ; ++i)
    {
        maxA[i] = max(max(a[i], maxA[i - 1] * a[i]), minA[i - 1] * a[i]);
        minA[i] = min(min(a[i], maxA[i - 1] * a[i]), minA[i - 1] * a[i]);
        value = max(value, maxA[i]);
    }
    return value;
}

C/C++代码二：

/*
 给定一个浮点数数组，有正有负数，0，正数组成,数组下标从1算起
 求最大连续子序列乘积，并输出这个序列，如果最大子序列乘积为负数，那么就输出-1
 用Max[i]表示以a[i]结尾乘积最大的连续子序列
 用Min[i]表示以a[i]结尾乘积最小的连续子序列  因为有复数，所以保存这个是必须的
*/
void longest_multiple(double *a, int n)
{
    double *Min = new double[n + 1]();
    double *Max = new double[n + 1]();
    double *p = new double[n + 1]();
    //初始化
    for (int i = 0; i <= n; i++)
    {
        p[i] = -1;
    }
    Min[1] = a[1];
    Max[1] = a[1];
    double max_val = Max[1];
    for (int i = 2; i <= n; i++)
    {
        Max[i] = max(Max[i - 1] * a[i], Min[i - 1] * a[i], a[i]);
        Min[i] = min(Max[i - 1] * a[i], Min[i - 1] * a[i], a[i]);
        if (max_val < Max[i])
            max_val = Max[i];
    }
    if (max_val < 0)
        printf("%d", -1);
    else
        printf("%d", max_val);
    //内存释放
    delete [] Max;
    delete [] Min;
}

变种

此外，此题还有另外的一个变种形式，即给定一个长度为N的整数数组，只允许用乘法，不能用除法，计算任意（N-1）个数的组合中乘积最大的一组，并写出算法的时间复杂度。

我们可以把所有可能的（N-1）个数的组合找出来，分别计算它们的乘积，并比较大小。由于总共有N个（N-1）个数的组合，总的时间复杂度为O（N2），显然这不是最好的解法。

OK，以下解答来自编程之美

解法1

解法2、

此外，还可以通过分析，进一步减少解答问题的计算量。假设N个整数的乘积为P，针对P的正负性进行如下分析（其中，AN-1表示N-1个数的组合，PN-1表示N-1个数的组合的乘积）。

  1. P为0

那么，数组中至少包含有一个0。假设除去一个0之外，其他N-1个数的乘积为Q，根据Q的正负性进行讨论：

Q为0
说明数组中至少有两个0，那么N-1个数的乘积只能为0，返回0；
Q为正数
返回Q，因为如果以0替换此时AN-1中的任一个数，所得到的PN-1为0，必然小于Q；
Q为负数
如果以0替换此时AN-1中的任一个数，所得到的PN-1为0，大于Q，乘积最大值为0。

  1. P为负数

根据“负负得正”的乘法性质，自然想到从N个整数中去掉一个负数，使得PN-1为一个正数。而要使这个正数最大，这个被去掉的负数的绝对值必须是数组中最小的。我们只需要扫描一遍数组，把绝对值最小的负数给去掉就可以了。

  1. P为正数

类似地，如果数组中存在正数值，那么应该去掉最小的正数值，否则去掉绝对值最大的负数值。
上面的解法采用了直接求N个整数的乘积P，进而判断P的正负性的办法，但是直接求乘积在编译环境下往往会有溢出的危险（这也就是本题要求不使用除法的潜在用意），事实上可做一个小的转变，不需要直接求乘积，而是求出数组中正数（+）、负数（-）和0的个数，从而判断P的正负性，其余部分与以上面的解法相同。

在时间复杂度方面，由于只需要遍历数组一次，在遍历数组的同时就可得到数组中正数（+）、负数（-）和0的个数，以及数组中绝对值最小的正数和负数，时间复杂度为O（N）。

参考文献及推荐阅读

  1. 杨氏矩阵查找、最大乘积连续子串、字符串循环右移、社区很忙等5题集中讨论地址；
  2. http://www.bjwilly.com/archives/395.html；