1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
|
import java.util.Scanner;
public class PlacingParen {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String exp = scanner.next();
System.out.println(getMaxValue(exp));
}
public static long getMaxValue(String exp) {
int x = exp.length();
int[] d = new int[(x + 1) / 2];
char[] op = new char[(x - 1) / 2];
for (int i = 0; i < x - 1; i = i + 2) {
d[i / 2] = Character.getNumericValue(exp.charAt(i));
op[i / 2] = exp.charAt(i + 1);
}
d[(x + 1) / 2 - 1] = Character.getNumericValue(exp.charAt(x - 1));
return getMaxValue(d, op);
}
private static long getMaxValue(int[] d, char[] op) {
long[][] m = new long[d.length][d.length];
long[][] M = new long[d.length][d.length];
for (int i = 0; i < d.length; i++) {
m[i][i] = d[i];
M[i][i] = d[i];
}
for (int s = 0; s < op.length; s++) {
for (int i = 0; i < d.length - s; i++) {
int j = i + s + 1;
if (j >= d.length)
break;
long[] tempMinAndMax = minAndMax(m, M, op, i, j);
m[i][j] = tempMinAndMax[0];
M[i][j] = tempMinAndMax[1];
}
}
return M[0][d.length - 1];
}
private static long[] minAndMax(long[][] m, long[][] M, char[] op, int i, int j) {
long min = Long.MAX_VALUE;
long max = Long.MIN_VALUE;
for (int k = i; k < j; k++) {
long a = eval(M[i][k], M[k + 1][j], op[k]);
long b = eval(M[i][k], m[k + 1][j], op[k]);
long c = eval(m[i][k], M[k + 1][j], op[k]);
long d = eval(m[i][k], m[k + 1][j], op[k]);
min = Math.min(min, Math.min(a, Math.min(b, Math.min(c, d))));
max = Math.max(max, Math.max(a, Math.max(b, Math.max(c, d))));
}
long[] result = { min, max };
return result;
}
private static long eval(long a, long b, char op) {
if (op == '+') {
return a + b;
} else if (op == '-') {
return a - b;
} else if (op == '*') {
return a * b;
} else {
assert false;
return 0;
}
}
}
|
