Max Value using +, * and ()

第二轮是一个abc或者中国人，口语屌炸。问了我第二个intern proj。 开始想出Bigint，我说已经在电面做过了。 然后他就另外出了一个找最大值的题。给一个数组[1,1,2,1]，然后用+ * （）三个操作求出这个数组的最大值，这个题返回6。 很简单，DP解决。我开始写了个用res[i][j] 表示的solution，然后写完代码，测了几个用例，都过了。然后他问如果数组里面有负数和0咋办呢。 我说维护两个表max[i][j] 和 min[i][j]。然后他很满意。我说其实还有复杂度更低的方法，可以用一位数组做。他说不用了，这个方法已经够好了，不要求写那么复杂。 然后面完还有10分钟，他问我有什么问题没有，我一听慌了，连时间都没有用完是不是不好，我就问他这个是不是没面好的征兆。他说不是不是，因为我已经很快给出solution，而且代码也没有问题，还给出了follow up的思路，就够了，说有时候时间没用完也是面的好的表现。 我听完心里放松了一些，然后和他唠了唠team之间的工作什么的，只是为了把时间耗完

public class Solution {

public int getMax(int[] nums) {

int n = nums.length;

int maxResult[][] = new int[n][n];

for (int len = 1; len <= n; len++) {

for (int start = 0; start < n; start++) {

int end = start + len - 1;

if (end >= n) {

continue;

}

if (start == end) {

maxResult[start][end] = nums[start];

continue;

}

for (int mid = start; mid < end; mid++) {

maxResult[start][end] = Math.max(maxResult[start][end],

Math.max(maxResult[start][mid] + maxResult[mid + 1][end],

maxResult[start][mid] * maxResult[mid + 1][end]));

}

}

}

return maxResult[0][n - 1];

}

public static void main(String args[]) {

Solution solution = new Solution();

System.out.println(solution.getMax(new int[] { 1, 1, 2, 1 }));

}

}