我要招人

去企业版

首页 > 试题广场 >

整数成绩最大化

[编程题]整数成绩最大化

热度指数：2646 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给出一个整数n，将n分解为至少两个整数之和，使得这些整数的乘积最大化，输出能够获得的最大的乘积。

例如：

2=1+1，输出1；

10=3+3+4，输出36。

输入描述:

输入为1个整数

输出描述:

输出为1个整数

示例1

输入

输出

算法知识视频讲解

Python 3

TS9527

有两种方法解决该题：

解法一：动态规划

记数j的最大分解乘积为prod[j]。对于数k，我们可以依次遍历i = 1, ..., k - 1，计算i * prod[k - i]的最大值然后取max。当然了，这个过程当中可能存在k - i > prod[k - i]的情况（因为在统计prod[k - i]时，我们没有考虑k - i = 0 + (k - i)这种情况，不符合题目要求分解为两个正整数），这个时候我们要取的乘积就变成了i * (k - i)。也就是说，从数学上来说，有状态转移方程 $prod[k] = \max{}_{i = 1, .., k - 1} \max(i \times prod[k - i], i \times (k - i))$

根据这个方程遍历到n即可。

AC代码：

class MainActivity:

    def main(self):
        # Read the data
        n = int(input())
        # Initialization
        maxProd = [1]
        # Traverse
        for num in range(1, n):
            realNum = num + 1
            tmpResult = float('-inf')
            for subtractNum in range(1, realNum):
                subtractResult = realNum - subtractNum
                subtractResultIdx = subtractResult - 1
                tmpResult = max(tmpResult, subtractNum * maxProd[subtractResultIdx], subtractNum * subtractResult)
            maxProd.append(tmpResult)
        print(maxProd[-1])


if __name__ == '__main__':
    M = MainActivity()
    M.main()

这个时间复杂度应该在O(n²)的样子，AC运行时间是45ms。

解法二：数学（均值不等式）

我们假设可以把n分解为k个正整数 $a_1, a_2, ..., a_k$ ，那么该问题就变成了已知 $\Sigma_{i = 1}^{k}a_{i} = n$ 的前提下求 $\prod_{i = 1}^{k}a_i$ 的最大值。根据均值不等式 $(\prod_{i = 1} ^ {k}a_{i})^\frac{1}{k} \leq \frac{\Sigma_{i = 1}^{k}a_i}{k} = \frac{n}{k}$ ，我们很容易确定在 $a_i > 0$ 且为实数的情况下有 $\prod_{i = 1}^{k}a_i$ 的最大值为 $(\frac{n}{k})^k$ ，取得该最大值的条件是 $a_1 = a_2 = ... = a_k = \frac{n}{k}$ 。

然而，由于题目正整数的限制，我们只能让 $a_i$ 在 $\frac{n}{k}$ 周围取整（除非这个结果就是个整数，那直接取它就行）。我们记 $\lfloor\frac{n}{k}\rfloor = t$ ，则对于任意 $a_i$ 均应为 $t$ 或 $t + 1$ 。假设有 $p$ 个元素取 $t$ ，则会有 $k - p$ 个元素取 $t + 1$ 。根据题目限制，应有 $tp + (t + 1)(k - p) = n$ ，很容易解得 $p = kt + k - n$ 。因此，分解成 $k$ 个数的最大乘积应为 $t^{kt + k - n}\times(t + 1)^{n - kt}$ 。

我们遍历k = 1, ..., n，并每次取max，就可以得到最终结果，即最终结果为 $\max{}_{k = 1}^{n} \lfloor\frac{n}{k}\rfloor^{k\lfloor\frac{n}{k}\rfloor + k - n}\cdot(\lfloor\frac{n}{k} \rfloor+ 1)^{n - k\lfloor\frac{n}{k}\rfloor}$

AC代码：

class MainActivity:

    def main(self):
        # Read the data
        n = int(input())
        # Initialization
        result = float('-inf')
        # Traverse
        for k in range(1, n + 1):
            if n % k:
                lowNum = n // k
                highNum = lowNum + 1
                result = max(result, lowNum ** (k * lowNum + k - n) * highNum ** (n - k * lowNum))
            else:
                result = max(result, (n // k) ** k)
        print(result)


if __name__ == '__main__':
    M = MainActivity()
    M.main()

遍历的时间复杂度是O(n)，但我感觉乘方也挺耗时间的，看乘方做快速幂优化才行吧。

发表于 2024-08-26 15:09:36 回复(0)

提交观点

问题信息

C++工程师 iOS工程师安卓工程师运维工程师前端工程师算法工程师 PHP工程师贪心动态规划 2018 数学 Java工程师招商银行信用卡中心

上传者：小小

难度：

1条回答 76收藏 7215浏览

通过挑战的用户

查看代码

牛客68457...

2023-03-04 19:55:50
优秀的大魔王不愿吃饼

2023-01-11 16:44:39
liu12345

2022-10-01 17:39:15
getmsi

2022-09-25 19:35:25
牛客11351...

2022-09-19 10:46:48