Java recursive solution with memoization


  • 0
    Q

    Don't need to know anything about math. I divide number in 2 equals (or almost equal if it's odd), and find max for each half, then keep reducing one number by one, and increasing another number by one, and calculating new max. Once the value starts going down I exit the loop.

      public class Solution {
        	public int integerBreak(int n) {
        	    if (n <= 3) return n-1;
        	    if (mem.containsKey(n)) return mem.get(n);
        		int n1 = n/2, n2 = n - n1;
        		int max = 0,  max1 = 1;
        		while (n1>=2 && max1>=max){
        			max1 = Math.max(n1, integerBreak(n1))*Math.max(n2, integerBreak(n2));
        			if (max1 >= max){ 
        				max = max1;
        				n1--;
        				n2++;
        			}
        		}
        		mem.put(n, max);
        		return max;
        	}
            private Map<Integer, Integer> mem = new HashMap<Integer, Integer>();
        }

Log in to reply
 

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