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

程序员编程艺术第二十八~二十九章：最大连续乘积子串、字符串编辑距离 第二十八~二十九章：最大连续乘积子串、字符串编辑距离 前言 时间转瞬即逝，一转眼，又有4个多月没来更新blog了，过去4个月都在干啥呢？对的，今2013年元旦和朋友一起搭了个方便朋友们找工作的编程面试算法论坛：为学论坛。最近则在负责一款在线编程挑战平台--英雄会的产品运营，当然拉，虽说是产品运营，实际上身兼“数职”：出题审题，写代码测试一个不落下。 最近跟百度的几个朋友线下闲聊，听他们说，百度校招群内的不少朋友在找工作的时候都看过我的blog，一听当即便激起了自己重写更新此blog的欲望，恰巧眼下阳春三月(虽说已是3月，奇妙的是，前两天北京还下了一场大雪)，又到了找工作的季节(相对于每年的9月份来说，3月则是一个小高潮)，那就从继续更新专为找工作准备笔试面试的程序员编程艺术开始吧。 本文讲两个问题， 第二十八章、最大连续乘积子串， 第二十九章、字符串编辑距离， 这两个问题皆是各大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，而他们的最长公共子序列是adf。LCS可以使用动态规划法解决。 解答： 解法一、两个for循环直接轮询 或许，读者初看此题，自然会想到最大乘积子序列问题类似于最大子数组和问题：/v_JULY_v/article/details/6444021，最简单粗暴的方式便是用链两个for循环直接轮询。 for (int i=0;inum;i++) { double x=arrs[i]; for (int j = i+1; j num; j++) { x*=arrs[j]; if(xmax){ max=x; start=arrs[i]; end=arrs[j]; } } 解法二、虽说类似于最大子数组和问题，可以用两个for循环直接轮询搞定，但实际上具体处理起来诸多不同，为什么呢，因为乘积子序列中有正有负也还可能有0。我们可以把问题简化成这样：数组中找一个子序列，使得它的乘积最大；同时找一个子序列，使得它的乘积最小（负数的情况）。因为虽然我们只要一个最大积，但由于负数的存在，我们同时找这两个乘积做起来反而方便。也就是说，不但记录最大乘积，也要记录最小乘积。So，我们让 maxCurrent表示当前最大乘积的candidate， minCurrent反之，表示当前最小乘积的candidate（用candidate这个词是因为只是可能成为新一轮的最大/最小乘积）， 而maxProduct则记录到目前为止所有最大乘积candidates的最大值。 由于空集的乘积定义为1，在有哪些信誉好的足球投注网站数组前，maxCurrent,minCurrent,maxProduct都赋为1。 假设在任何时刻你已经有了maxCurrent和minCurrent这两个最大/最小乘积的candidates，新读入数组的元素x(i)后，