LeetCode最大化得分算法疑问：子数组计算逻辑错误排查

问题回顾 #

给你一个由n个正整数组成的数组nums和整数k，初始得分为1。你可以执行最多k次以下操作来最大化得分：

• 选择一个未选过的非空子数组nums[l,...,r]；
• 在该子数组中选择素数得分最高的元素x；若有多个，选索引最小的；
• 将得分乘以x。

其中，整数x的素数得分是其不同质因数的个数，返回最大可能得分（结果对10^9+7取模）。

你的错误原因 #

你对有效子数组数量的计算逻辑是正确的，错误出在幂运算的手动计算失误：

• 你计算的(22011 * 14858^5) MOD (10^9+7)结果为719826932，但正确的计算结果应为256720975，和LeetCode的正确答案一致。
• 验证：用快速幂正确计算14858^5 mod 1e9+7得到544284985，再乘以22011后取模，结果正好是256720975。

方法可行性分析 #

你的核心思路（计算每个元素作为贡献元素的有效子数组数量，按素数得分从高到低优先使用元素）是完全可行的，这也是官方解法的核心逻辑：

1. 先计算每个元素的素数得分；
2. 对每个元素，找到其作为“子数组中素数得分最高且索引最小”的元素时，对应的有效子数组数量；
3. 将元素按素数得分降序排序，依次取min(剩余k, 有效子数组数量)，将得分乘以该元素的对应次幂（取模），直到k用完。

而单调栈的作用，正是高效计算每个元素的有效子数组范围：

• 对每个元素i，用单调栈找到左侧第一个素数得分≥当前得分的元素位置L（无则为-1）；
• 找到右侧第一个素数得分>当前得分的元素位置R（无则为n，n为数组长度）；
• 有效子数组数量为(i - L) * (R - i)，这和你用(l+1)*(r+1)的本质完全一致——你定义的l是向左可移动步数，r是向右可移动步数，l+1对应i-L，r+1对应R-i，只是表述方式不同。

总结 #

你的方法完全可行，错误仅在于手动计算幂运算时的失误。使用快速幂（而非手动计算）可以避免这类错误，同时用单调栈高效找到每个元素的有效子数组范围，就能正确解决问题。

内容的提问来源于stack exchange，提问作者Yousef Marey