代码拉取完成，页面将自动刷新
同步操作将从 doocs/leetcode 强制同步，此操作会覆盖自 Fork 仓库以来所做的任何修改，且无法恢复！！！
确定后同步将在后台操作，完成时将刷新页面，请耐心等待。
给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
示例 1:
输入: 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2:
输入: 10 输出: 36 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
说明: 你可以假设 n 不小于 2 且不大于 58。
动态规划。
设 dp[i] 表示正整数 n 能获得的最大乘积，初始化 dp[1] = 1。
i >= 2 时，dp[i] = max(dp[i], dp[i - j] * j, (i - j) * j)（j∈[0, i)）。
class Solution:
def integerBreak(self, n: int) -> int:
dp = [1] * (n + 1)
for i in range(2, n + 1):
for j in range(1, i):
dp[i] = max(dp[i], dp[i - j] * j, (i - j) * j)
return dp[n]
class Solution {
public int integerBreak(int n) {
int[] dp = new int[n + 1];
dp[1] = 1;
for (int i = 2; i <= n; ++i) {
for (int j = 1; j < i; ++j) {
dp[i] = Math.max(Math.max(dp[i], dp[i - j] * j), (i - j) * j);
}
}
return dp[n];
}
}
class Solution {
public:
int integerBreak(int n) {
vector<int> dp(n + 1);
dp[1] = 1;
for (int i = 2; i <= n; ++i) {
for (int j = 1; j < i; ++j) {
dp[i] = max(max(dp[i], dp[i - j] * j), (i - j) * j);
}
}
return dp[n];
}
};
func integerBreak(n int) int {
dp := make([]int, n+1)
dp[1] = 1
for i := 2; i <= n; i++ {
for j := 1; j < i; j++ {
dp[i] = max(max(dp[i], dp[i-j]*j), (i-j)*j)
}
}
return dp[n]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
此处可能存在不合适展示的内容，页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容，可点击提交进行申诉，我们将尽快为您处理。