顿搜
飞过闲红千叶，夕岸在哪
类目归类
[LeetCode 343] Integer Break [Java] [Runtime : 1MS]
09/02
1. Description
Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get.
You may assume that n is not less than 2 and not larger than 58.
2. Runtime Distribution
3. Submission Details
4. Example
given n = 2, return 1 (2 = 1 + 1); given n = 10, return 36 (10 = 3 + 3 + 4).
5. Code
public int integerBreak(int n) {
if (n < 2) {
return 0;
}
int[] dp = new int[n + 1];
dp[1] = 1;
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= i - j; j++) {
dp[i] = Math.max(dp[i], j * dp[i - j]);
}
if (i < n && dp[i] < i) {
dp[i] = i;
}
}
return dp[n];
}6.Test
public class LeetCode0343 {
public int integerBreak(int n) {
if (n < 2) {
return 0;
}
int[] dp = new int[n + 1];
dp[1] = 1;
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= i - j; j++) {
dp[i] = Math.max(dp[i], j * dp[i - j]);
}
if (i < n && dp[i] < i) {
dp[i] = i;
}
}
return dp[n];
}
public static void main(String[] args) {
LeetCode0343 leetcode = new LeetCode0343();
System.out.println(leetcode.integerBreak(10));
}
}
