Easy Java DP solution 7 lines


  • 0
    S
    • Since input is a non-negative integer, we don't need to consider n = 0 situation.
      Using DP method it to get the induction from n = 1.
    public class Solution {
        public int integerBreak(int n) {
           int[] array = new int[n + 1];
           for (int i = 1; i <= n; i++) {
               for (int j = 1; j < i; j++) {
                   // here use DP, array[i] means the max product when n = i
                   array[i] = Math.max(Math.max(array[j], j) * (i-j), array[i]);
               }
           }
           return array[n];
        }
    }
    

Log in to reply
 

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