Massive Algorithms: [Algo] Maximum Expression Value 表达式最大值

[Algo] Maximum Expression Value 表达式最大值 - SegmentFault

给定一个整数数组，要求在数字之间任意添加乘号，加号和括号，使得最后表达式结果最大。比如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 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;
    }

Maximum Expression Value II
给定一个整数数组，要求在数字之间任意添加乘号，加号和括号，使得最后表达式结果最大。比如1121,最大值为(1+1)*(2+1)，这里数字可以是0或者负数。

解法和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;
}

Q：如果输入是double数组怎么办？
A: 一样的做法，用第二题的解肯定没问题。
Read full article from [Algo] Maximum Expression Value 表达式最大值 - SegmentFault

[Algo] Maximum Expression Value 表达式最大值 - SegmentFault

Labels

Popular Posts