# Brute force with memory in case of your interviewer forbid tricky solution

• This is an Amazon interview question that could be solved in a very tricky way. Since a lot of people have already posted their solutions, I just post a brute force solution in case of the interviewer want a normal way.

I use recursion. For each recursion, I find the maximum result and also the minimum result. For example, if you want to know the maximum result of A/B, where A and B are also some expressions, then you only need to know the maximum result of A and the minimum result of B. However, if you want to know the maximum result of C/(A/B), then you also need to know the minimum result of A/B. That's why both maximum and minimum should be stored.

``````// by fallcreek
public class Solution {

public String optimalDivision(int[] nums) {
Map<String, pair> memory = new HashMap<>();
pair sol = divid(nums,0,nums.length-1, memory);
return sol.maxS;
}

public pair divid(int[] nums, int start, int end, Map<String, pair> memory){
String key = start + " " + end;
if(memory.containsKey(key)) return memory.get(key);
if(start == end)    return new pair(nums[start], "" + nums[start],nums[start], "" + nums[start]);

pair sol = new pair(0,"",0,"");

for(int i = start; i < end; i++){
pair left = divid(nums, start, i, memory);
pair right = divid(nums, i + 1, end, memory);

double min = left.min / right.max;
String minS = left.minS + "/" + (i + 1 == end ? right.maxS : "(" + right.maxS + ")");
double max = left.max / right.min;
String maxS = left.maxS + "/" + (i + 1 == end ? right.minS : "(" + right.minS + ")");
if(sol.min == 0 || min < sol.min){
sol.min = min;
sol.minS = minS;
}
if(max > sol.max){
sol.max = max;
sol.maxS = maxS;
}
}
memory.put(key, sol);
return sol;
}
}

class pair{
double min;
String minS;
double max;
String maxS;

public pair(double min, String minS, double max, String maxS){
this.min = min;
this.minS = minS;
this.max = max;
this.maxS = maxS;
}
}
``````

• This is very helpful! Thanks for sharing.

• can you explain a little bit on when to choose to add parentheses? thanks

• Love this solution. Now we are at least learning something.

• Thanks, it's a good solution

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