DP Solution which also works for positive float point numbers

• Since the numbers are positive integers, there is some shortcut. If the numbers are positive double/float numbers. Then only DP solution is available?

``````public class Solution {

private void postprocess(int[] nums, byte[][] ind, int s, int e, boolean findmin, boolean sndpart, StringBuilder res){
if( s == e){ // obvious the fst part
res.append(nums[s]);
}else{
if(sndpart){
res.append('(');
}
int div = findmin?ind[e][s]:ind[s][e];
postprocess(nums, ind, s, div, findmin, false, res);
res.append('/');
postprocess(nums, ind, div + 1, e, !findmin, true, res);
if(sndpart){
res.append(')');
}
}
}

public String optimalDivision(int[] nums) {
int len = nums.length;
double[][] max = new double[len][len];
byte[][] ind = new byte[len][len];
for(int i = 0; i < len; i++){
max[i][i] = nums[i];
}
double mx, mi;
for(int L = 1; L <= len - 1; L++){
for(int s = 0; s < len - L; s++){
for(int j = s; j < s + L; j++){
mx = max[s][j]/max[s+L][j+1];
mi = max[j][s]/max[j+1][s+L];
if(mx > max[s][s+L]){
max[s][s+L] = mx;
ind[s][s+L] = (byte)j;
}
if(max[s+L][s] == 0.0 || mi < max[s+L][s]){
max[s+L][s] = mi;
ind[s+L][s] = (byte)j;
}
}
}
}

StringBuilder res = new StringBuilder();
postprocess(nums, ind, 0, nums.length - 1, false, false, res);
return res.toString();
}
}
``````

• Float point version with a simple test case which is more interesting:

``````public class Solution {

private void postprocess(double[] nums, byte[][] ind, int s, int e, boolean findmin, boolean sndpart, StringBuilder res){
if( s == e){ // obvious the fst part
res.append(nums[s]);
}else{
if(sndpart){
res.append('(');
}
int div = findmin?ind[e][s]:ind[s][e];
postprocess(nums, ind, s, div, findmin, false, res);
res.append('/');
postprocess(nums, ind, div + 1, e, !findmin, true, res);
if(sndpart){
res.append(')');
}
}
}

public String optimalDivision(double[] nums) {
int len = nums.length;
double[][] max = new double[len][len];
byte[][] ind = new byte[len][len];
for(int i = 0; i < len; i++){
max[i][i] = nums[i];
}
double mx, mi;
for(int L = 1; L <= len - 1; L++){
for(int s = 0; s < len - L; s++){
for(int j = s; j < s + L; j++){
mx = max[s][j]/max[s+L][j+1];
mi = max[j][s]/max[j+1][s+L];
if(mx > max[s][s+L]){
max[s][s+L] = mx;
ind[s][s+L] = (byte)j;
}
if(max[s+L][s] == 0.0 || mi < max[s+L][s]){
max[s+L][s] = mi;
ind[s+L][s] = (byte)j;
}
}
}
}

StringBuilder res = new StringBuilder();
postprocess(nums, ind, 0, nums.length - 1, false, false, res);
return res.toString();
}

public static void main(String[] args){
Solution sol = new Solution();
System.out.println(sol.optimalDivision(new double[]{100, 10, 0.3, 5, 0.5})); \\ output 100.0/10.0/(0.3/(5.0/0.5))
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.