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

[restabs alignment="osc-tabs-right" responsive="true" icon="true" text="More" seltabcolor="#fdfdfd" seltabheadcolor="#000" tabheadcolor="blue"]
[restab title="Java" active="active"]

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];
}

[/restab]
[/restabs]

6.Test

[restabs alignment="osc-tabs-right" responsive="true" icon="true" text="More" seltabcolor="#fdfdfd" seltabheadcolor="#000" tabheadcolor="blue"]
[restab title="Java" active="active" ]

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));
	}
}

[/restab]
[/restabs]