Skip to content

Latest commit

 

History

History
311 lines (252 loc) · 12.4 KB

28.0.md

File metadata and controls

311 lines (252 loc) · 12.4 KB

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

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

OK，欢迎朋友们在本文下参与讨论，如果在线编译自己的代码（编程语言任选C/C++/Java/C#），可以上英雄会提交你的代码，有任何问题，欢迎随时不吝批评或指正，感谢。

题目描述：

**给一个浮点数序列，取最大乘积连续子串的值，例如 -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;     
}

代码二：思路，记录以第i个结尾的最大乘积M和最小乘积m，并且记录这两个区间的起点（终点都是i），不断更新，来源：

pair<int,int> maxproduct(double *f,int n)
{   //返回最大乘积的起点终点
    int R = 0, r = 0;   //最大最小区间的 起点
    pair<int,int> ret = make_pair(0, 0);   //最大 最小的区间下标
    double M = f[0], m = f[0], answer = f[0];     // 最大 最小值
    for (int i = 1; i < n; ++i)
    {
        double t0 = f[i] * M, t1 = f[i] * m;  
        if (t0 > t1)
        {
            M = t0;  
            m = t1;  
        }  
        else
        {
            int t = R;  
            R = r;  
            r = t;  
            M = t1;  
            m = t0;  
        }  
        if (M < f[i])
        {
            M = f[i];  
            R = i;  
        }  
        if (m > f[i])
        {
            m = f[i];  
            r = i;  
        }  
        if (answer < M)
        {
            answer = M;  
            ret = make_pair(R, i);  
        }  
    }  
    return ret;  
}

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

C#版完整代码(代码来自参加英雄会在线编程挑战之1019、最大乘积连续子串的在线提交代码的用户)：

//答题英雄：danielqkj  
using System;  
public class Test   
{  
    void Max(double a, double b, double c)  
    {  
        double d = (a>b)?a:b;  
        return (d>c)?d:c;      
    }  
      
    void Min(double a, double b, double c)  
    {  
        double d = (a>b)?b:a;  
        return (d>c)?c:d;  
    }  
      
      
    public static void Main()  
    {  
        int n = Int32.parse(Console.readline());  
        double[] a = new double[n];  
        double maxvalue = a[0];  
        double[] max = new double[n];  
        double[] min = new double[n];  
        double start, end;  
          
        String[] s = Console.readline().split(' ');  
        for (int i = 0; i < n; i++)  
        {  
            a[i] = Double.parse(s[i])  
        }  
          
        max[0] = a[0];  
        min[0] = a[0];  
        start = 0, end = 0;  
          
        for (int i = 1; i < n; i++)  
        {  
            max[i]=Max(a[i], a[i]*max[i-1], a[i]*min[i-1]);  
            min[i]=Min(a[i], a[i]*max[i-1], a[i]*min[i-1]);  
              
            if (max[i] > maxvalue)  
            {  
                maxvalue = max[i];  
                end = i;  
            }  
        }  
          
        double mmm = maxvalue;  
        while ( (mmm - 0.0) > 0.00001 )  
        {  
            start = end;  
            mmm = mmm / a[start];  
        }  
          
        Console.Writeline(a[start] + " " + a[end] + " " + maxvalue);  
          
    }  
}

变种

此外，此题还有另外的一个变种形式，即给定一个长度为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。

2.P为负数

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

3.P为正数

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

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

##参考文献及推荐阅读

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

July、二零一三年三月二十一日。