前言 时间转瞬即逝，一转眼，又有4个多月没来更新blog了，过去4个月都在干啥呢？对的，今2013年元旦和朋友利用业余时间一起搭了个方便朋友们找工作的编程面试算法论坛：为学论坛http://www.51weixue.com/。最近则开始负责一款在线编程挑战平台：英雄会的产品运营http://hero.pongo.cn/，当然拉，虽说是产品运营，实际上身兼“数职”：出题审题，写代码测试，制定比赛规则等等一个都不敢落下。 前几天跟百度的几个朋友线下闲聊，听他们说，百度校招群内的不少朋友在找工作的时候都看过我的blog，一听当即便激起了自己重写此blog的欲望，恰巧眼下阳春三月(虽说已是3月，奇妙的是，前两天北京还下了一场大雪)，又是找工作的季节(相对于每年的9月份来说，3月则是一个小高潮)，那就从继续更新专为IT人员找工作时准备笔试面试的程序员编程艺术系列开始吧。 再者从去年4月份上传的编程艺术前27章的PDF文档的1.3万下载量来看http://download.csdn.net/detail/v_july_v/4256339，此系列确确实实帮助了成千上万的人。Yeah，本文讲两个问题，
- 第二十八章、最大连续乘积子串，
- 第二十九章、字符串编辑距离，
这两个问题皆是各大IT公司最喜欢出的笔试面试题，比如说前者是小米2013年校招笔试原题，而后者则更是反复出现，如去年9月26日百度一二面试题，10月9日腾讯面试题第1小题，10月13日百度2013校招北京站笔试题第二 大道题第3小题，及去年10月15日2013年Google校招笔试最后一道大题皆是考察的这个字符串编辑距离问题。 OK，欢迎朋友们在本文下参与讨论，如果用Java/C#的朋友想在线编译自己的代码，可以上英雄会提交你的代码，有任何问题，欢迎随时不吝批评或指正，感谢。
第二十九章、最大连续乘积子串
题目描述：给一个浮点数序列，取最大乘积连续子串的值，例如 -2.5，4，0，3，0.5，8，-1，则取出的最大乘积连续子串为3，0.5，8。也就是说，上述数组中，3 0.5 8这3个数的乘积3*0.5*8=12是最大的，而且是连续的。
提醒：此最大乘积连续子串与最大乘积子序列不同，请勿混淆，前者子串要求连续，后者子序列不要求连续。也就是说：最长公共子串（Longest CommonSubstring）和最长公共子序列（LongestCommon Subsequence，LCS）的区别： 子串（Substring）是串的一个连续的部分， - 子序列（Subsequence）则是从不改变序列的顺序，而从序列中去掉任意的元素而获得的新序列；
更简略地说，前者（子串）的字符的位置必须连续，后者（子序列LCS）则不必。比如字符串acdfg同akdfc的最长公共子串为df，而它们的最长公共子序列LCS是adf，LCS可以使用动态规划法解决。
解答：
解法一、穷举，所有的计算组合：
或许，读者初看此题，自然会想到最大乘积子序列问题类似于最大子数组和问题：http://blog.csdn.net/v_JULY_v/article/details/6444021，可能立马会想到用最简单粗暴的方式：两个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;
-
-
- 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;
-
-
- }
- return maxProduct;
- }
代码二：思路，记录以第i个结尾的最大乘积M和最小乘积m，并且记录这两个区间的起点（终点都是i），不断更新，来源http://www.51weixue.com/thread-246-1-1.html： - 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;
- }
解法三、
本题除了上述类似最大子数组和的解法，也可以直接用动态规划求解（其实，上述的解法一本质上也是动态规划，只是解题所表现出来的具体形式与接下来的解法二不同罢了。这个不同就在于下面的解法二会写出动态规划问题中经典常见的状态转移方程，而解法一是直接求解）。具体解法如下：
假设数组为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++代码： -
-
-
-
-
-
- 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、最大乘积连续子串：http://hero.pongo.cn/Question/Details?ID=19&ExamID=19的在线提交代码的用户)： -
- 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);
-
- }
- }
提炼简化下上面的核心代码为： - 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;
- }
| 
