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

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

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

相关阅读

相关最大乘积问题

题目描述输入n个元素组成的序列s，找出一个乘积最大的连续子序列，输出最大乘积的值。如果这个最大乘积不是正数，输出0。n小于18，每个元素值的绝对值不大于10。输入

朱雀/ 2023年06月25日 10:15/ 0 赞/ 165 阅读

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

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

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

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

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

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

相关 1007 最大乘积

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

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

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

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

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

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

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

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

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

相关 1017 乘积最大

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

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

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

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