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

心已赠人 2022-07-14 03:00 150阅读 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 条评论，150人围观）

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

相关阅读

相关 343. Integer Break

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

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

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

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

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

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

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

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

相关 1007 最大乘积

Description 设有一个长度为N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1个部分的乘积能够为最大。同时，为了帮助

矫情吗；*/ 2022年09月11日 12:25/ 0 赞/ 157 阅读

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

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

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

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

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

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

相关 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 赞/ 151 阅读

相关 1017 乘积最大

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

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

相关 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 赞/ 144 阅读

相关 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 赞/ 357 阅读