摘要:给定一个整数数组,要求在数字之间任意添加乘号,加号和括号,使得最后表达式结果最大。这时最大值,更新。而本题中可以有和负数,所以我们要把最大表先初始化为负最大值,最小表初始化为正最小值。
Maximum Expression Value I
动态规划 复杂度给定一个整数数组,要求在数字之间任意添加乘号,加号和括号,使得最后表达式结果最大。比如1121,最大值为(1+1)*(2+1),所有数字都是正数。
时间O(n^2) 空间O(N^2)
思路先假设没有乘号,那最大值就是所有数加起来,然后我们考虑将其分段加入乘号,如果某一段是加号,和其他段相乘,那我们就认为那段加号的就被加了个括号。所以我们分段的过程其实就加了括号了。但是这么多数字我们可以分很多不同段,如果用搜索的话难免会有重复计算,所以这里用到动态规划,假设dp[i][j]表示总长为i的一段数字,其中前j长的哪一段中可以包含乘号,所能产生的最大值,这么一来,假设题目所给的数字有n个,那dp[n][n]就是这所有的数字组合起来既有加号又有乘号的式子的最大值了。再假设sum(k, i)表示所给数字从第k个到第i个数字的和。递推式为dp[i][j] = max(dp[i][j], dp[k][j - 1] * sum(k + 1, i)),这里i >= k >= j。其中后半部分dp[k][j - 1] * sum(k + 1, i)表示,我们把总长为i的数字分割成前k个,和k + 1到最后两部分。前半部分最大值已知,我们用它来乘以后半部分的和,用这种方法来决定哪一段只用加号。
举例说明,假设所给数字为
3 2 6
我们可以有最大值3 * 2 * 6 = 36,一开始我们有:
sum: 3 5 11 j=0 j=1 j=2 j=3 dp: i=0 0 0 0 0 i=1 0 3 0 0 i=2 0 5 0 0 i=3 0 11 0 0
由于总长为i,其中前1位数字可以包含乘号的情况,就是所有数字都不包含乘号,所以最大值就是累加值。然后我们看总长为2开始(总长为1就是第一个数,没有计算的必要),前2位数字可以包含乘号的情况,这里我们可以有分割点k = 1时,是3 + 2 = 5和k = 2时是3 * 2 = 6两种情况(k表示从第k位开始只有加号)。这时最大值6,更新dp[2][2]。
j=0 j=1 j=2 j=3 dp: i=0 0 0 0 0 i=1 0 3 0 0 i=2 0 5 6 0 i=3 0 11 0 0
然后我们看总长为3开始(总长为1就是第一个数,没有计算的必要),前2位数字可以包含乘号的情况。这里k=2时,3 * (2 + 6) = 24, k=3时,6 * 6 = 36(第一个6是dp[2][2],第二个6是我们所给数字中的6)
j=0 j=1 j=2 j=3 dp: i=0 0 0 0 0 i=1 0 3 0 0 i=2 0 5 6 0 i=3 0 11 24 36
更新完dp[3][3]我们也就计算完所有情况了,这时可知最大值是36.
注意全局最大max在第一个用于累加的for循环后,要置为dp[n][0],否则我们会把全部数字加起来这个组合给漏掉。
代码public class MaxValueAddingOperator { public int solve(int[] nums){ int n = nums.length; int[] sum = new int[n + 1]; int[][] dp = new int[n + 1][n + 1]; // 初始化累加数组,还有不用乘号的情况 for(int idx = 1; idx <= n; idx++){ sum[idx] = sum[idx - 1] + nums[idx - 1]; dp[idx][1] = sum[idx]; } int max = dp[n][0]; // 对于总长为numOfDigitsInTotal的数字序列 for(int numOfDigitsInTotal = 2; numOfDigitsInTotal <= n; numOfDigitsInTotal++){ // 前numOfDigitsWithMult个数字可以包含乘号来计算的话 for(int numOfDigitsWithMult = 2; numOfDigitsWithMult <= numOfDigitsInTotal; numOfDigitsWithMult++){ // 从splitPointBetweenAddAndMult开始只用加号的话,求最大值 for(int splitPointBetweenAddAndMult = numOfDigitsWithMult; splitPointBetweenAddAndMult <= numOfDigitsInTotal; splitPointBetweenAddAndMult++){ dp[numOfDigitsInTotal][numOfDigitsWithMult] = Math.max(dp[numOfDigitsInTotal][numOfDigitsWithMult], dp[splitPointBetweenAddAndMult - 1][numOfDigitsWithMult - 1] * (sum[numOfDigitsInTotal] - sum[splitPointBetweenAddAndMult - 1])); } if(numOfDigitsInTotal == n && dp[n][numOfDigitsWithMult] > max){ max = dp[n][numOfDigitsWithMult]; } } } return max; } public static void main(String[] args){ MaxValueAddingOperator mvao = new MaxValueAddingOperator(); int[] arr = {3, 2, 6}; int[] arr2 = {1, 1, 2, 1}; System.out.println(mvao.solve(arr)); System.out.println(mvao.solve(arr2)); } }Maximum Expression Value II
动态规划 复杂度给定一个整数数组,要求在数字之间任意添加乘号,加号和括号,使得最后表达式结果最大。比如1121,最大值为(1+1)*(2+1),这里数字可以是0或者负数。
时间O(n^2) 空间O(N^2)
思路解法和I是一样的,不过这里我们要维护一个最大表和一个最小表,这样,每次我们要乘的那个数是正数时,我们的最大值就是之前的最大值乘以这个正数,最小值就是之前的最小值乘以这个正数。如果要乘的是个负数的话,我们的最大值就是之前的最小值乘以这个正数,最小值就是之前的最大值乘以这个正数。另外,我们还要先初始化这个两个表,因为之前那题结果肯定大于0,所以我们不用初始化,不管怎么算原先矩阵中的0都会被替换掉。而本题中可以有0和负数,所以我们要把最大表先初始化为负最大值,最小表初始化为正最小值。
代码public int solve2(int[] nums){ int n = nums.length; int[] sum = new int[n + 1]; int[][] dpMax = new int[n + 1][n + 1]; int[][] dpMin = new int[n + 1][n + 1]; // 初始化最大表最小表 for(int idx1 = 1; idx1 <=n; idx1++){ for(int idx2 = 1; idx2 <=n; idx2++){ dpMax[idx1][idx2] = Integer.MIN_VALUE; } } for(int idx1 = 1; idx1 <=n; idx1++){ for(int idx2 = 1; idx2 <=n; idx2++){ dpMin[idx1][idx2] = Integer.MAX_VALUE; } } // 初始化累加表 for(int idx = 1; idx <= n; idx++){ sum[idx] = sum[idx - 1] + nums[idx - 1]; dpMax[idx][1] = sum[idx]; dpMin[idx][1] = sum[idx]; } int max = dpMax[n][1]; for(int numOfDigitsInTotal = 2; numOfDigitsInTotal <= n; numOfDigitsInTotal++){ for(int numOfDigitsWithMult = 2; numOfDigitsWithMult <= numOfDigitsInTotal; numOfDigitsWithMult++){ for(int splitPointBetweenAddAndMult = numOfDigitsWithMult; splitPointBetweenAddAndMult <= numOfDigitsInTotal; splitPointBetweenAddAndMult++){ int partialSum = sum[numOfDigitsInTotal] - sum[splitPointBetweenAddAndMult - 1]; // 根据待会要乘的数的正负号,来判断我们乘的对象是最大表还是最小表 if(partialSum < 0){ dpMax[numOfDigitsInTotal][numOfDigitsWithMult] = Math.max(dpMax[numOfDigitsInTotal][numOfDigitsWithMult], dpMin[splitPointBetweenAddAndMult - 1][numOfDigitsWithMult - 1] * partialSum); dpMin[numOfDigitsInTotal][numOfDigitsWithMult] = Math.min(dpMin[numOfDigitsInTotal][numOfDigitsWithMult], dpMax[splitPointBetweenAddAndMult - 1][numOfDigitsWithMult - 1] * partialSum); } else { dpMax[numOfDigitsInTotal][numOfDigitsWithMult] = Math.max(dpMax[numOfDigitsInTotal][numOfDigitsWithMult], dpMax[splitPointBetweenAddAndMult - 1][numOfDigitsWithMult - 1] * partialSum); dpMin[numOfDigitsInTotal][numOfDigitsWithMult] = Math.min(dpMin[numOfDigitsInTotal][numOfDigitsWithMult], dpMin[splitPointBetweenAddAndMult - 1][numOfDigitsWithMult - 1] * partialSum); } } if(numOfDigitsInTotal == n && dpMax[n][numOfDigitsWithMult] > max){ max = dpMax[n][numOfDigitsWithMult]; } } } return max; }后续 Follow Up
Q:如果输入是double数组怎么办?
A: 一样的做法,用第二题的解肯定没问题。
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/66181.html
摘要:输入的模块上使用。我们看到它包含一个庞大的属性列表。默认地,它返回当前模块的属性列表。 Python Learn Part More_Info Content List 1.Python Introduce 1.1 python REPL 1.2 python helloworld.py 1.3 python help() 1.4 to python_string 1.5 dif...
摘要:是的内置模板引擎,在此之前使用过,不过刚刚打开看了下,已经停止更新,并且将要被所替代。如果需要进行一些条件判断,则使用。我们就主要说一下不常用的或者其他模板引擎里没有的一些功能。 template7是framework7的内置模板引擎,在此之前使用过jquery-tmpl,不过刚刚打开github看了下,已经停止更新,并且将要被JsRender所替代。妹的,JsRender又是什么鬼啊...
摘要:是的内置模板引擎,在此之前使用过,不过刚刚打开看了下,已经停止更新,并且将要被所替代。如果需要进行一些条件判断,则使用。我们就主要说一下不常用的或者其他模板引擎里没有的一些功能。 template7是framework7的内置模板引擎,在此之前使用过jquery-tmpl,不过刚刚打开github看了下,已经停止更新,并且将要被JsRender所替代。妹的,JsRender又是什么鬼啊...
阅读 2751·2021-11-19 11:30
阅读 3039·2021-11-15 11:39
阅读 1765·2021-08-03 14:03
阅读 1969·2019-08-30 14:18
阅读 2026·2019-08-30 11:16
阅读 2116·2019-08-29 17:23
阅读 2581·2019-08-28 18:06
阅读 2514·2019-08-26 12:22