343. Integer Break （划分整数使乘积最大）

心已赠人 2022-07-14 03:00 209阅读 0赞

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 and not larger than 58.

Hint:

1.  There is a simple O(n) solution to this problem.
2.  You may check the breaking results of n ranging from 7 to 10 to discover the regularities.

**题目大意：给定一个正整数n，将n划分为至少两个数，找到一种方案，使得这些数相加的和等于n，并且这些数的乘积达到最大。（默认n的取值范围为\[2,58\]）**

**解题思路：**

当n=2时，只能划分为1\*1；

当n=3时，只能划分为2\*1；

当 n=4 时，可以划分为2\*2（或者不划分也是一样的）；

当n>=5时，3\*(n-3) >= 2\*(n-2) > n，所以划分为3\*(n-3)，再对(n-3)继续进行划分。

代码如下：（0ms，beats 50.31%）

public class Solution {
        public int integerBreak(int n) {
            if (n <= 3)
    			return n - 1;
    		int product = 1;
    		while (n > 4) {
    			product *= 3;
    			n -= 3;
    		}
    		product *= n;
    		return product;
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，209人围观）

还没有评论，来说两句吧...

相关阅读

相关 343. Integer Break

把一个整数拆分成至少两个正整数的和，要求拆分后的整数的乘积最大。 Example 1: Input: 2 Output: 1 Explanation

柔情只为你懂/ 2023年03月13日 13:11/ 0 赞/ 76 阅读

相关 LeetCode:343. Integer Break整数拆分（C语言）

题目描述：给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。返回你可以获得的最大乘积。示例 1: 输入: 2 输出: 1 解释:

迈不过友情╰/ 2023年03月03日 06:21/ 0 赞/ 47 阅读

相关 leetcode 343. Integer Break | 343. 整数拆分（Java）

题目 [https://leetcode.com/problems/integer-break/][https_leetcode.com_problems_integer

╰半夏微凉°/ 2023年01月24日 02:12/ 0 赞/ 116 阅读

相关乘积(整数最大连续乘积问题)

大贤者福尔的数学研究成绩斐然，影响力越来越大，也有很多人向他请教。最近，有人咨询他一个问题。给定若干个整数S=S1,S2,...,Sn，其中若干个连续的数的最大乘积是多少？

超、凢脫俗/ 2022年10月12日 12:19/ 0 赞/ 288 阅读

相关【日常学习】【划分DP】codevs1017 乘积最大题解

题目来源 2000NOIP 题目描述 Description 今年是国际数学联盟确定的“2000——世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的

╰半夏微凉°/ 2022年08月04日 04:08/ 0 赞/ 317 阅读

相关算法1.复数乘积和整数划分问题

1. 设![这里写图片描述][SouthEast] (1) 算法设计思路 xy=(ac-bd)+(ad+bc)i可以转换成xy=(ac-bd)+((a+b)(c+d)-

末蓝、/ 2022年07月14日 13:39/ 0 赞/ 253 阅读

相关 343. Integer Break （划分整数使乘积最大）

Given a positive integer n, break it into the sum of at least two positive integers and

心已赠人/ 2022年07月14日 03:00/ 0 赞/ 210 阅读

相关 1017 乘积最大

题目描述 Description 今年是国际数学联盟确定的“2000——世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生

港控/mmm°/ 2022年06月18日 09:50/ 0 赞/ 270 阅读

相关 leetcode 343. Integer Break 深度优先遍历DFS(超时) + 最大子元素乘积 + 发现规律

Given a positive integer n, break it into the sum of at least two positive integers and

系统管理员/ 2022年06月07日 01:15/ 0 赞/ 198 阅读

相关 LeetCode:343. Integer Break 拆分整数保持乘积最大

试题： Given a positive integer n, break it into the sum of at least two positive integer

- 日理万妓/ 2021年06月24日 16:10/ 0 赞/ 437 阅读