程序员编程艺术第二十八~二十九章：最大连续乘积子串、字符串编辑距离

第二十八~二十九章：最大连续乘积子串、字符串编辑距离

前言

时间转瞬即逝，一转眼，又有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可以使用动态规划法解决。

解答：

解法一、想当然的用两个for循环直接轮询
或许，读者初看此题，自然会想到最大乘积子序列问题类似于最大子数组和问题：http://blog.csdn.net/v_JULY_v/article/details/6444021，可能立马会想到用最简单粗暴的方式：两个for循环直接轮询。

    解法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.在给定位置上插入一个字符
   2.替换任意字符
   3.删除任意字符
写一个程序，返回最小操作数，使得对源串进行这些操作后等于目标串，源串和目标串的长度都小于2000。

提醒：上文前言中已经说过了，此题反复出现，最近考的最多的是百度和Google的笔试面试经常考察。下图则是2013年Google的校招试题原景重现：
解答：
    解法一、    此题跟上面的最大连续乘积子串类似，常见的思路是动态规划，下面是简单的DP状态方程：
In the above alignment, space (‘_’) is introduced to both strings. There are 5 matches, 1
mismatch, 1 insert, and 1 delete.The alignment has similarity score 7.
    A_CAATCC
    AGCA_TGC
    Note that the above alignment has the maximum score.Such alignment is called optimal
alignment.String alignment problem tries to find the alignment with the maximum similarity
score!String alignment problem is also called global alignment problem.
Needleman-Wunsch algorithm
    Consider two strings S[1..n] and T[1..m].Define V(i, j) be the score of the optimal alignment
between S[1..i] and T[1..j].
Basis:
V(0, 0) = 0
V(0, j) = V(0, j-1) + d(_, T[j])：Insert j times
V(i, 0) = V(i-1, 0) + d(S, _)：Delete i times
that is:
Example :
下面是代码，测试数据比较少，若有问题请指正：

    这样，很快就可以完成一个递归程序，如下所示：
     可以看到，圈中的两个子问题被重复计算了。为了避免这种不必要的重复计算，可以把子问题计算后的解存储起来。如何修改递归程序呢？还是DP！请看此链接：http://www.cnblogs.com/yujunyong/articles/2004724.html。 补充
此外，关于这个“编辑距离”问题的应用：搜索引擎关键字查询中拼写错误的提示，可以看下这篇文章：http://www.ruanyifeng.com/blog/2012/10/spelling_corrector.html。关于什么是“编辑距离”：一个快速、高效的Levenshtein算法实现，这个是计算两个字符串的算法，Levenshtein距离又称为“编辑距离”，是指两个字符串之间，由一个转换成另一个所需的最少编辑操作次数。当然，次数越小越相似。这里有一个BT树的数据结构，挺有意思的：http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees；最后，Lucene中也有这个算法的实现(我想，一般的搜索引擎一般都应该会有此项拼写错误检查功能的实现)：http://www.bjwilly.com/archives/395.html。扩展：面试官还可以继续问下去，那么，请问，如何设计一个比较两篇文章相似性的算法？这个问题的讨论可以看看这里：http://t.cn/zl82CAH。

后记    有种人喜欢远观代码，以欣赏代码的角度阅读代码，所谓如镜中美女只可远观不可亵玩焉，发现自己也陷入了这种境地。昨天买的一本《提高C++性能的编程技术》，书不错，推荐给大家。    想看编程面试算法题的讲解，就进blog；想参与笔试面试题的讨论，就上为学论坛；想在线刷笔试面试题，就上英雄会，祝各位好运，享受生活，享受工作，享受思考和编码的乐趣。    July、二零一三年三月二十一日。
5楼zhaoyl03昨天 23:52
感谢博主提供的最大连续乘积子串的动态求解思路，代码很清楚。不过，也正是因为清楚，发现解法2那个c++代码的瑕疵，maxProduct 等的初值不能取为1，而应该取数组的第一个值，循环从i=1开始，否则像数组A=[-2.5,0,-1,0,-0.5,0,-1]就会返回最大的连乘值是1，但是实际上是0.我是不是太吹毛求疵了？
4楼pyemma昨天 22:43
顶，最喜欢楼主写的算法系列了，好好学习，向大牛看齐，最近正想申请亚研院的实习生，打算好好复习复习算法
3楼hww836967373昨天 19:10
占座学习，thanks
2楼v_JULY_v昨天 18:12
怎么有2条评论没显示了？...n程序员编程艺术第二十八~二十九章：最大连续乘积子串、字符串编辑距离nliuxiaobin_bluegiant: 针对最大连续乘积子串问题，本人已经使用了JAVA实现了其功能，见博客http://blog.csdn...nn程序员编程艺术第二十八~二十九章：最大连续乘积子串、字符串编辑距离nhww836967373: 占座学习，thanksnn程序员编程艺术第二十八~二十九章：最大连续乘积子串、字符串编辑距离npyemma: 顶，最喜欢楼主写的算法系列了，好好学习，向大牛看齐，最近正想申请亚研院的实习生，打算好好复习复习算法
Re: liuxiaobin_bluegiant昨天 18:04
针对最大连续乘积子串问题，本人已经使用了JAVA实现了其功能，见博客http://blog.csdn.net/liuxiaobin_bluegiant/article/details/8702698nn，欢迎大家发言评论。同时向v_JULY_v请教，算法哪个更优？