/** * 给定一个正整数 n,将其拆分为至少两个正整数的和,并使这些整数的乘积最大化。 返回你可以获得的最大乘积。 * https://leetcode-cn.com/problems/integer-break/solution/zheng-shu-chai-fen-by-leetcode-solution/ */ public class MaxIntegerBreak { /** * 第一时间想到了动态规划 * 最大乘积 肯定会变成 max = i * j * 问题就在于这个 i 或者 j 是否是其他整数乘积所得 * 假设i不变,那么两种情况: * 只拆分两个正整数 : max = i * (n -i) * 多个情况 max = Math.max(i*(n-i),i* max(n-i)); * * max(n-i)可以使用数组存储起来,存的就是n-i可获得最大乘积 * * @param n * @return */ public static int integerBreak(int n) { int dp[] = new int[n + 1]; for (int i = 2; i <= n; i++) { int max = 0; for (int j = 1; j < i; j++) { max = Math.max(max, Math.max(j * (i - j), j * dp[i - j])); } dp[i] = max; } return dp[n]; } /** * 数学推导 * @param n * @return */ public static int integerBreak2(int n) { if (n <= 3) { return n - 1; } int quotient = n / 3; int remainder = n % 3; if (remainder == 0) { return (int) Math.pow(3, quotient); } else if (remainder == 1) { return (int) Math.pow(3, quotient - 1) * 4; } else { return (int) Math.pow(3, quotient) * 2; } } public static void main(String[] args) { int result = integerBreak(10); System.out.println(result); } }