343. Integer Break

题目：
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.

For example, given n = 2, return 1 (2 = 1 + 1); given n = 10, return 36 (10 = 3 + 3 + 4).

Note: you may assume that n is not less than 2.

解答：
这里我提供了两个办法，一种是我用dp的办法解的，还有一种是参考别人的数学解法：
DP解法：

//State: f[i] is when sum is i the largest product we can get
//Function: f[i] = max(f[i - j] * j), i >= 2, i - j >= 1
//Initialize: f[1] = f[2] = 1;
//Result: f[n]
public int integerBreak(int n) {
int[] f = new int[n + 1];
Arrays.fill(f, 1);

    for (int i = 3; i 

数学解法：

//A more mathematic solution
//We can prove that when N is even, N/2 N/2 is largest; when N is odd, (N - 1)/2 (N + 1)/2 is the largest
//Also we have N/2 N/2 > N --> N > 4
// (N - 1)/2 (N + 1)/2 > N --> N >= 5
//So when N > 4, we can do the calculation
public int integerBreak(int n) {
if (n == 2) return 1;
if (n == 3) return 2;

    int result = 1;    while (n > 4) {        result *= 3;        n -= 3;    }    result *= n;    return result;}

关键字：leetcode, 算法, int, return

版权声明

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处。如若内容有涉嫌抄袭侵权/违法违规/事实不符，请点击 举报 进行投诉反馈！