package com.algorithm.dynamicprogramming;

/**
 * 算法描述：给定一个正整数n，将其分解为至少两个正整数的和，并使这些整数的乘积最大化。返回您可以获得的最大产品。
 * For example, given n = 2, return 1 (2 = 1 + 1); given n = 10, return 36 (10 = 3 + 3 + 4).
 * @author rich
 *
 */
public class MaxMulti {
    
    
    public static void main(String[] args) {
        System.out.println(maxMutil(10));
    }
    /**
     * 算法分析：n = 2 :(2=1+1) 1
     * n = 3 : (3=2+1) 2 
     * n = 4 : (4 = 2+2) 4 
     * n = 5 : (5=3+2) 6 
     * n = 6 : (6 = 3+3) 9
     * n = 7 : (7 = 3+ 4) 12
     * n = 8 : (8=3+3+2) 18
     * n = 9 : (9 = 3+3+3) 27 
     * n = 10 :(10 = 3+3+4) 36 
     * f(n) = max(max(f(n),j*(n-j)),j * f(n-j))
     * @param n
     * @return
     */
    public static int maxMutil(int n) {
        int[] memo = new int[n+1];
        if (n == 2) return 1;
        for (int i = 3 ;i<=n;i++) {
            for (int j = 2; j<i;j++) {
                memo[i] = Math.max(Math.max(memo[i], j * (i-j)), j * memo[i-j]);
            }
        }
        return memo[n];
    }
}