1000ms

Difficulty: 7

所属公司 : 科大讯飞

时间 :2025年9月13日

算法与标签>滑动窗口

会员或题库专享

请先，开通会员或购买题库科大讯飞机考编程题库，可解锁完整内容。

购买科大讯飞机考编程题库开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（科大讯飞机考编程题库），可解锁完整内容。

购买题库开通会员

思路

这个问题可以分解为两个主要步骤：

高效计算每个数字的重量。
在计算出的重量序列上，寻找长度不超过 $k$ 的最大连续子段和。

题目内容

一个大于 $1$ 的正整数 $x$ 的重量定义为：将其分解质因数之后得到的最大的指数。例如， $90= 2^1×3^2×5^1$ ，它的重量为 $max$ { $1,2,1$ } $=2$ 。

现在，给定 $n$ 个整数 $a_1,a_2,…,a_n$ ，小歪想找到这样不超过 $k$ 个连续的位置，满足：它们上面数字的重量之和是最大的。你只需要输出这个最大的重量之和即可。