免费制作网站net域名,自己建设一个平台网站多少钱,企业网站建设实训心得,安卓市场官方版简介Kadane算法及相关的普通动态规划
本文详细论述Kadane算法的经典题目#xff0c;并通过“首先列出动态规划解法#xff0c;再改为Kadane算法解法”的方式#xff0c;讲解二者的不同。最后给出一道Kadane算法变体的题目#xff0c;解法极为简洁优美。
Kadane算法也是一…简介Kadane算法及相关的普通动态规划
本文详细论述Kadane算法的经典题目并通过“首先列出动态规划解法再改为Kadane算法解法”的方式讲解二者的不同。最后给出一道Kadane算法变体的题目解法极为简洁优美。
Kadane算法也是一种动态规划算法它的时间复杂度也是O(n), 但它与普通的动态规划有什么不同呢这里先给出结论不同就是它的空间复杂度是O(1)而普通动态规划的空间复杂度是O(n).
下面的例题-1是一道经典的可以用Kadane算法求解的题目。
例题-1 LeetCode-53
给定一个整数数组求它的子数组之和的最大值。 比如数组为[-2,1,-3,4,-1,2,1,-5,4], 则子数组元素之和最大为6因为当子数组为 [4,-1,2,1]时可取得最大值。
解法-1. 普通动态规划法
众所周知动态规划法需要有一个递推公式。这个公式的思考与解析如下。 假设有一个同样大小的dp数组其第i个位置的元素dp[i]的含义是原整数数组s从0至i处且包含元素i时的所有子数组中子数组元素之和的最大值。 听见来很拗口是不是。说白了就是对于所有的以s[i]为最右元素的子数组求子数组元素之和最大的那个值就是dp[i]. 想一想如果我们知道了所有的dp[0], dp[1], …,dp[size-1], 那么我们是不是就知道了子数组之和的最大值了呢。 这里要注意的是当 i j size 时 dp[i] 有可能大于 dp[j]. 知道 dp[i] 的定义后那么 dp[i1] 是什么呢 很明显dp[i] 与 dp[i1] 的差异就在于原数组的第 i1 个元素即 s[i1]. 一种可能是s[i1]可以被继续累加到当前最大值上即dp[i]和s[i1]都是非负数那么 dp[i1] dp[i] s[i1] 另一种可能是s[i1]不可以被继续累加到当前最大值上 比如dp[i]是负数而s[i1]又比dp[i]大, 于是只好从s[i1]开始算即 dp[i1] s[i1] 综合这2个式子dp[i1] max(dp[i]s[i1], s[i1]) 换一种写法 dp[i] max(dp[i-1]s[i], s[i]) 在当前定义下我们最后需要返回 dp 数组中的最大元素。
这里有一个问题为什么不能把 dp[i] 定义为“从0至i处的所有子数组中子数组元素之和的最大值”呢 如果可以这么定义的话那么我们就不需要在dp数组中找一个最大值而只要返回dp数组的最后一个元素即可了。 其实对于有些问题时完全可以这么做的比如下面的例题-2. 但是对于例题-1来说鉴于其所求是子数组元素之和的最大值它相当于对之前的多个元素有依赖关系如果那样定义的话则无法建立dp[i1]和dp[i]之间的递推关系。 这个问题是一个隐藏较深且不太容易解释的问题。喜欢对算法作深入思考的朋友可以多想想这里看是否有更加简洁精辟的见解。
普通动态规划法的代码还是比较简洁的如下
class Solution {public int maxSubArray(int[] nums) {int [] dp new int [nums.length];dp[0] nums[0];int result nums[0];for (int i1; inums.length; i) {dp[i] Math.max(nums[i], nums[i]dp[i-1]);result Math.max(result, dp[i]);}return result;}
}解法-2. Kadane算法
上面的整个dp数组是否必要呢 其实不是必要的。公式中的 dp[i] 和 dp[i-1] 看似不同但其实可以巧妙地用一个变量来代表从而整个dp数组也就不需要了 – 只用一个变量来维护dp[i]. 所以Kadane算法的空间复杂度是O(1). 这个技巧还是很值得学习的。
代码如下
class Solution {public int maxSubArray(int[] nums) {int max_here nums[0];int result nums[0];for (int i1; inums.length; i) {max_here Math.max(nums[i], nums[i]max_here);result Math.max(result, max_here);}return result;}
}例题-1中对于dp[i]的定义还是不那么符合人的直觉的而下面例题-2对 dp[i] 的设定则非常直接了。
例题-2. LeetCode-121
给定一个整数数组其中每一个数字代表了股票在当天的价格。你每天只能操作一次这一次是买或者卖股票请最大化利润。 比如[7,1,5,3,6,4]最大化利润是5. 因为在价格为1的那天买在价格为6的那天卖可以得到5的利润。
解法-1. 普通动态规划法
有了前面那么难的题这题就简单了。对于动态规划就是主要要考虑递推公式。 设定一个同样大小的数组dp那么很自然地就想到 dp[i] 就代表到当天为止的最大利润。 那么dp[i1]是什么呢 假设原数组叫prices, 此时相当于多了一个 prices[i1], 所引起的变化就是也许 prices[i1] 能得到更高利润。 怎么会得到更高利润呢如果用prices[i1]减去之前的最小值则是它得到的利润值如果这个值比dp[i]大则有了更高利润。 由此可见要记录一个历史最小值。这个并不难实现。 这样一分析递推公式就出来了 dp[i1] max(dp[i], prices[i1]-minValue) 由此也可见我们最后需要返回的就是 dp[size-1]即dp数组的最后一个元素。
普通动态规划法代码如下
int maxProfit(vectorint prices) {if (prices.empty()) return 0;vectorint dp(prices.size());dp[0] 0;int minPrice prices[0];for (int i1; iprices.size(); i) {dp[i] max(dp[i-1], prices[i] - minPrice);if (prices[i] minPrice) minPrice prices[i];}return dp[prices.size()-1];
}解法-2. Kadane算法
仍然对普通动态规划法稍作优化用一个变量代替dp[i]和dp[i1], 由此消除dp数组。 代码如下
int maxProfit(vectorint prices) {if (prices.empty()) return 0;int max_here 0;int minPrice prices[0];for (int i1; iprices.size(); i) {max_here max(max_here, prices[i] - minPrice);if (prices[i] minPrice) minPrice prices[i];}return max_here;
}除了上面2道例题有的时候会出现 Kadane 算法的变体。这个时候需要因为一些特殊条件而做出一些巧妙的变化则可以继续使用Kadane算法。
例题-3 LeetCode-152
给定一个整数数组求其子数组的乘积最大值。 比如[2,3,-2,4]其子数组乘积最大值为6因为 2x36.
首先还是要找出递推数组。假设dp[i]为“至位置i处的包含了位置i的子数组乘积最大值”那么对于例子中给定的数组对应的dp数组是这样的[2, 6, -2, 4] 所以 dp[i1] max(dp[i]*s[i1], s[i]) 由此似乎可以写出程序了。和例题-1很像嘛是不是直接套就可以了 但注意这样的数组 [-2, 3, -4], 很明显答案是24但应用上面算法的dp数组是 [-2, 3, 3]. 原因很简单每遇到负数一次则结果反转也就是说如果应用了上面的算法则-2无法被后面再一次遇到负数时用上。 换句话说尽管dp[1]为3是正确的但dp[2]还是3就不正确了而此时dp[0]或原数组nums[0]的信息无法被dp[2]用上。 至此普通的动态规划似乎不再能够应用了因为递推关系似乎无法推出来。怎么办呢其实Kadane算法仍可以应用。 鉴于负数每乘一次都会反转结果我们就只好一直乘直至结尾。如果负数的个数是偶数则这就是结果先不考虑0。 但如果负数的个数是奇数比如1个那我们就不知道是在这个负数的左边还是右边会出现乘积最大值了。 这又怎么办呢也很好办。从左往右和从右往左分别扫一遍。因为我们不可能在一遇到负数的时候就重启计算。 最后一旦遇到0怎么办呢这就要重启计算了。相当于数字0将数组分段了。一旦遇到0则从0后面的第1个数字开始重启我们的乘法运算直至下一个0或数组在当前方向上结束。 啰里吧嗦说了很多但代码其实还是很简洁的。
class Solution {public int maxProduct(int[] nums) {long r1 Integer.MIN_VALUE;long p1 1;for (int i0; inums.length; i) {p1 p1 * nums[i];if (p1 r1) r1 p1;if (p1 0) p1 1;}long r2 Integer.MIN_VALUE;long p2 1;for (int inums.length-1; i0; i--) {p2 p2 * nums[i];if (p2 r2) r2 p2;if (p2 0) p2 1;}return (int)(r1r2?r1:r2);}
}由本题可见Kadane算法其实可能比普通动态规划更加灵活。
(END)
