面试必备：高频算法题汇总「图文解析 + 教学视频 + 范例代码」之 字符串处理+动态规划 汇总！ (5)

温馨提示，如果思维不好理解的话，把解题思路记清楚就行

public int minDistance(String word1, String word2) { // write your code here int n = word1.length(); int m = word2.length(); int[][] dp = new int[n + 1][m + 1]; for (int i = 0; i < n + 1; i++){ dp[i][0] = i; } for (int j = 0; j < m + 1; j++){ dp[0][j] = j; } for (int i = 1; i< n + 1; i++){ for (int j = 1; j < m + 1; j++){ if (word1.charAt(i - 1) == word2.charAt(j - 1)){ dp[i][j] = dp[i - 1][j - 1]; } else { dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], Math.min(dp[i][j - 1], dp[i - 1][j])); } } } return dp[n][m]; } 复杂度分析

时间复杂度 ：\(O(m n)\)，两层循环显而易见。
空间复杂度 ：\(O(m n)\)，循环的每一步都要记录结果。

乘积最大子序列

给定一个整数数组 nums ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。

示例 :

输入: [-2,0,-1] 输出: 0 解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。 解题思路

遍历数组时计算当前最大值，不断更新

令imax为当前最大值，则当前最大值为 imax = max(imax * nums[i], nums[i])

由于存在负数，那么会导致最大的变最小的，最小的变最大的。因此还需要维护当前最小值imin，imin = min(imin * nums[i], nums[i])

当负数出现时则imax与imin进行交换再进行下一步计算

public int maxProduct(int[] nums) { int max = Integer.MIN_VALUE, imax = 1, imin = 1; for(int i=0; i<nums.length; i++){ if(nums[i] < 0){ int tmp = imax; imax = imin; imin = tmp; } imax = Math.max(imax*nums[i], nums[i]); imin = Math.min(imin*nums[i], nums[i]); max = Math.max(max, imax); } return max; } 时间复杂度：

O(n)

Attention

为了提高文章质量，防止冗长乏味

下一部分算法题

本片文章篇幅总结越长。我一直觉得，一片过长的文章，就像一堂超长的 会议/课堂，体验很不好，所以我打算再开一篇文章

在后续文章中，我将继续针对链表 栈 队列 堆 动态规划 矩阵 位运算 等近百种，面试高频算法题，及其图文解析 + 教学视频 + 范例代码，进行深入剖析有兴趣可以继续关注 _yuanhao 的编程世界

不求快，只求优质，每篇文章将以 2 ～ 3 天的周期进行更新，力求保持高质量输出

# 相关文章

「面试原题 + 图文详解 + 实例代码」二叉搜索树-双指针-贪心 面试题汇总
面试高频算法题汇总「图文解析 + 教学视频 + 范例代码」之 二分 + 哈希表 + 堆 + 优先队列 合集