2941：子数组的最大 GCD-Sum（★★）

Ian

2015-01-01 约 375 字预计阅读 1 分钟次阅读

力扣第 2941 题

题目

给定一个整数数组 nums 和一个整数 k.

数组 a 的 gcd-sum 计算方法如下：

设 s 为 a 的所有元素的和。
设 g 为 a 的所有元素的 最大公约数。
a 的 gcd-sum 等于 s * g.

返回 nums 的至少包含 k 个元素的子数组的 最大 gcd-sum。

示例 1：

输入：nums = [2,1,4,4,4,2], k = 2
输出：48
解释：我们选择子数组 [4,4,4]，该数组的 gcd-sum 为 4 * (4 + 4 + 4) = 48。
可以证明我们无法选择任何其他 gcd-sum 大于 48 的子数组。

示例 2：

输入：nums = [7,3,9,4], k = 1
输出：81
解释：我们选择子数组 [9]，该数组的 gcd-sum 为 9 * 9 = 81。
可以证明我们无法选择任何其他 gcd-sum 大于 81 的子数组。

提示：

n == nums.length
1 <= n <= 10⁵
1 <= nums[i] <= 10⁶
1 <= k <= n

分析

典型的 log trick：固定子数组右端点，最多对应 log 段 gcd 值不同的子数组

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution:
    def maxGcdSum(self, nums: List[int], k: int) -> int:
        p = list(accumulate([0]+nums))
        res = 0
        sk = []
        for j,x in enumerate(nums):
            tmp,sk = sk,[[j,x]]
            for i,y in tmp:
                if gcd(x,y)<x:
                    x = gcd(x,y)
                    sk.append([i,x])
                else:
                    sk[-1][0] = i
            for i,y in sk:
                if j-i+1>=k:
                    res = max(res,y*(p[j+1]-p[i]))
        return res

1085 ms

目录

2941：子数组的最大 GCD-Sum（★★）

题目

分析

解答