SnapChat电面 - 求表达式的最大值

Question:

给定数组，只有正数，使用＋和＊和（）。求最大值。

 

Solution 1:

2维DP, O(N^3)

public int maxExprResult(int[] A) {
	int n = A.length;
	int[][] f = new int[n][n];
	for(int i=0; i<n; i++) {
		f[i][i] = A[i];
	}
	for(int w=2; w<=n; w++) { // window size of the sliding window
		for(int i=0, j=w-1; j<n; i++, j++) {
			for(int k=i; k<j; k++) {
				f[i][j] = Math.max(f[i][j], Math.max(f[i][k]+f[k+1][j], f[i][k]*f[k+1][j]));
			}
		}
	}
	return f[0][n-1];
}

 

 

Solution 2:

1维DP，O(N)

public int maxExprResult(int[] A) {
	int n = A.length;
	int[] k = new int[n];
    k[0] = A[0];
    
    for (int i = 1; i < n; i++) {
        k[i] = Math.max(k[i - 1] * A[i], (i >= 2 ? k[i - 2] : 1) * (A[i - 1] + A[i]));

        if (i >= 2) {
            k[i] = Math.max(k[i], (i >= 3 ? k[i - 3] : 1) * (A[i - 2] + A[i - 1] + A[i]));
        }
    }
    return k[n-1];
}