Integer Break Editorial


  • 0
    A

    Let the solution for a given number n is defined by sol(n)
    We can break n in following ways:
    (1, n - 1), (2, n - 2) ... (n - 1, n)
    In general we can define this as (i, n - i) for all i in [1..(n - 1)]
    We need to consider all of these n - 1 possibilities
    Hence recurrence relation for the solution can be defined as follows:

    sol(n) = max(i * (n - i), i * sol(n - i)) for all i in [1..(n - 1)]
    

    Now we need to define the base cases for this solution
    It is easy to verify that:

    sol(1) = 1 #reasonable assumption
    sol(2) = 1
    

    Now we can compute the required solution bottom up:

    int solve(int n) {
      int[] mem = new int[n + 1]
      if(n <= 2) return 1;
      mem[0] = 1;
      mem[1] = 1;
      for(i = 3; i <= n; i++)
        for (j = 1; j < i; j++) {
          mem[i] = j * (i - j);
          if(j * mem[i - j] > mem[i])
          mem[i] = j * mem[i - j];
        }
      return mem[n];
    }
    
    

Log in to reply
 

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