Java Solution, Backtracking


  • 15
    public class Solution {
        class Result {
            String str;
            double val;
        }
        
        public String optimalDivision(int[] nums) {
            int len = nums.length;
            return getMax(nums, 0, len - 1).str;
        }
        
        private Result getMax(int[] nums, int start, int end) {
            Result r = new Result();
            r.val = -1.0;
            
            if (start == end) {
                r.str = nums[start] + "";
                r.val = (double)nums[start];
            }
            else if (start + 1 == end) {
                r.str = nums[start] + "/" + nums[end];
                r.val = (double)nums[start] / (double)nums[end];
            }
            else {
                for (int i = start; i < end; i++) {
                    Result r1 = getMax(nums, start, i);
                    Result r2 = getMin(nums, i + 1, end);
                    if (r1.val / r2.val > r.val) {
                        r.str = r1.str + "/" + (end - i >= 2 ? "(" + r2.str + ")" : r2.str);
                        r.val = r1.val / r2.val;
                    }
                }
            }
            
            //System.out.println("getMax " + start + " " + end + "->" + r.str + ":" + r.val);
            return r;
        }
        
        private Result getMin(int[] nums, int start, int end) {
            Result r = new Result();
            r.val = Double.MAX_VALUE;
            
            if (start == end) {
                r.str = nums[start] + "";
                r.val = (double)nums[start];
            }
            else if (start + 1 == end) {
                r.str = nums[start] + "/" + nums[end];
                r.val = (double)nums[start] / (double)nums[end];
            }
            else {
                for (int i = start; i < end; i++) {
                    Result r1 = getMin(nums, start, i);
                    Result r2 = getMax(nums, i + 1, end);
                    if (r1.val / r2.val < r.val) {
                        r.str = r1.str + "/" + (end - i >= 2 ? "(" + r2.str + ")" : r2.str);
                        r.val = r1.val / r2.val;
                    }
                }
            }
            
            //System.out.println("getMin " + start + " " + end + "->" + r.str + ":" + r.val);
            return r;
        }
    }
    

  • 3
    Y
    This post is deleted!

  • 0

    Thank you for your good explanation!@yixuanwang-start


  • 0
    C

    nice solution!


  • 0
    C

    @shawngao Why is this solution backtracking? From what I can see the solution will try out all possible combinations. Great solution still, thank you.


  • 2
    S

    In fact, there is no need for backtracking, because the maximum could always be a1/(a2/a3/a4/...) = (a1*a3*a4*....)/a2.


  • 0
    F
    This post is deleted!

  • 0
    T

    @cgl_fai I agree with you. Actually, I think this solution is divide and conquer rather than backtracking.


  • 0
    A

    just dont understand why only when '''end - i >= 2 ? ''', we add parentheses?


Log in to reply
 

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