摘要：給定一個(gè)整數(shù)數(shù)組，要求在數(shù)字之間任意添加乘號(hào)，加號(hào)和括號(hào)，使得最后表達(dá)式結(jié)果最大。這時(shí)最大值，更新。而本題中可以有和負(fù)數(shù)，所以我們要把最大表先初始化為負(fù)最大值，最小表初始化為正最小值。

給定一個(gè)整數(shù)數(shù)組，要求在數(shù)字之間任意添加乘號(hào)，加號(hào)和括號(hào)，使得最后表達(dá)式結(jié)果最大。比如1121,最大值為(1+1)*(2+1)，所有數(shù)字都是正數(shù)。

時(shí)間O(n^2) 空間O(N^2)

先假設(shè)沒(méi)有乘號(hào)，那最大值就是所有數(shù)加起來(lái)，然后我們考慮將其分段加入乘號(hào)，如果某一段是加號(hào)，和其他段相乘，那我們就認(rèn)為那段加號(hào)的就被加了個(gè)括號(hào)。所以我們分段的過(guò)程其實(shí)就加了括號(hào)了。但是這么多數(shù)字我們可以分很多不同段，如果用搜索的話難免會(huì)有重復(fù)計(jì)算，所以這里用到動(dòng)態(tài)規(guī)劃，假設(shè)dp[i][j]表示總長(zhǎng)為i的一段數(shù)字，其中前j長(zhǎng)的哪一段中可以包含乘號(hào)，所能產(chǎn)生的最大值，這么一來(lái)，假設(shè)題目所給的數(shù)字有n個(gè)，那dp[n][n]就是這所有的數(shù)字組合起來(lái)既有加號(hào)又有乘號(hào)的式子的最大值了。再假設(shè)sum(k, i)表示所給數(shù)字從第k個(gè)到第i個(gè)數(shù)字的和。遞推式為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)表示，我們把總長(zhǎng)為i的數(shù)字分割成前k個(gè)，和k + 1到最后兩部分。前半部分最大值已知，我們用它來(lái)乘以后半部分的和，用這種方法來(lái)決定哪一段只用加號(hào)。
舉例說(shuō)明，假設(shè)所給數(shù)字為

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

由于總長(zhǎng)為i，其中前1位數(shù)字可以包含乘號(hào)的情況，就是所有數(shù)字都不包含乘號(hào)，所以最大值就是累加值。然后我們看總長(zhǎng)為2開始（總長(zhǎng)為1就是第一個(gè)數(shù)，沒(méi)有計(jì)算的必要），前2位數(shù)字可以包含乘號(hào)的情況，這里我們可以有分割點(diǎn)k = 1時(shí)，是3 + 2 = 5和k = 2時(shí)是3 * 2 = 6兩種情況（k表示從第k位開始只有加號(hào)）。這時(shí)最大值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

然后我們看總長(zhǎng)為3開始（總長(zhǎng)為1就是第一個(gè)數(shù)，沒(méi)有計(jì)算的必要），前2位數(shù)字可以包含乘號(hào)的情況。這里k=2時(shí)，3 * (2 + 6) = 24, k=3時(shí)，6 * 6 = 36(第一個(gè)6是dp[2][2]，第二個(gè)6是我們所給數(shù)字中的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]我們也就計(jì)算完所有情況了，這時(shí)可知最大值是36.

全局最大max在第一個(gè)用于累加的for循環(huán)后，要置為dp[n][0]，否則我們會(huì)把全部數(shù)字加起來(lái)這個(gè)組合給漏掉。

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];
        // 初始化累加數(shù)組，還有不用乘號(hào)的情況
        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];
        // 對(duì)于總長(zhǎng)為numOfDigitsInTotal的數(shù)字序列
        for(int numOfDigitsInTotal = 2; numOfDigitsInTotal <= n; numOfDigitsInTotal++){
            // 前numOfDigitsWithMult個(gè)數(shù)字可以包含乘號(hào)來(lái)計(jì)算的話
            for(int numOfDigitsWithMult = 2; numOfDigitsWithMult <= numOfDigitsInTotal; numOfDigitsWithMult++){
                // 從splitPointBetweenAddAndMult開始只用加號(hào)的話，求最大值
                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));
    }
}

給定一個(gè)整數(shù)數(shù)組，要求在數(shù)字之間任意添加乘號(hào)，加號(hào)和括號(hào)，使得最后表達(dá)式結(jié)果最大。比如1121,最大值為(1+1)*(2+1)，這里數(shù)字可以是0或者負(fù)數(shù)。

時(shí)間O(n^2) 空間O(N^2)

解法和I是一樣的，不過(guò)這里我們要維護(hù)一個(gè)最大表和一個(gè)最小表，這樣，每次我們要乘的那個(gè)數(shù)是正數(shù)時(shí)，我們的最大值就是之前的最大值乘以這個(gè)正數(shù)，最小值就是之前的最小值乘以這個(gè)正數(shù)。如果要乘的是個(gè)負(fù)數(shù)的話，我們的最大值就是之前的最小值乘以這個(gè)正數(shù)，最小值就是之前的最大值乘以這個(gè)正數(shù)。另外，我們還要先初始化這個(gè)兩個(gè)表，因?yàn)橹澳穷}結(jié)果肯定大于0，所以我們不用初始化，不管怎么算原先矩陣中的0都會(huì)被替換掉。而本題中可以有0和負(fù)數(shù)，所以我們要把最大表先初始化為負(fù)最大值，最小表初始化為正最小值。

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];
                // 根據(jù)待會(huì)要乘的數(shù)的正負(fù)號(hào)，來(lái)判斷我們乘的對(duì)象是最大表還是最小表
                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數(shù)組怎么辦？
A: 一樣的做法，用第二題的解肯定沒(méi)問(wèn)題。