Java simple O(n^2) AC solution


  • 0
    W
    public class Solution {
    public int integerBreak(int n) {
        if(n<=2) return 1;
        int bestBreakResult[] = new int[Math.max(5,n+1)];
        bestBreakResult[1] = 1; bestBreakResult[2]=1;             
        for(int i=2; i<=n; i++){
            for(int j=1; j<i-1; j++){
               bestBreakResult[i]=Math.max( bestBreakResult[i],
                   Math.max((i-j),bestBreakResult[i-j])
                   *Math.max(bestBreakResult[j],j));
            } 
        }
        return bestBreakResult[n];
    }}

Log in to reply
 

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