HardNo. 2941LeetCode Premium
Maximum GCD-Sum of a Subarray — LeetCode 2941 Python Solution
- Pattern
- Monotonic Stack
- Topics
- Array, Math, Binary Search, Number Theory
- Reading time
- 3 min
- Source
- leetcode.com
The problem
You are given an array of integers nums and an integer k. The gcd-sum of an array a is calculated as follows: Let s be the sum of all the elements of a.
Example
- Input
- nums = [2,1,4,4,4,2], k = 2
- Output
- 48
- Explanation
- We take the subarray [4,4,4], the gcd-sum of this array is 4 * (4 + 4 + 4) = 48.
Python solution
class Solution:
def maxGcdSum(self, nums: List[int], k: int) -> int:
s = list(accumulate(nums, initial=0))
f = []
ans = 0
for i, v in enumerate(nums):
g = []
for j, x in f:
y = gcd(x, v)
if not g or g[-1][1] != y:
g.append((j, y))
f = g
f.append((i, v))
for j, x in f:
if i - j + 1 >= k:
ans = max(ans, (s[i + 1] - s[j]) * x)
return ansComplexity
- Time
- O(log n) or O(n log n)
- Space · auxiliary
- O(1)
Pattern: Monotonic Stack
Answer "what is the next greater element" for every position in one pass. LeetCode 2941. Maximum GCD-Sum of a Subarray is filed here because the reference solution below belongs to the algorithm family this hub collects, even though its LeetCode tags point elsewhere.
The monotonic stack guide has the Python template for the pattern and the 225 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 2601 | Prime Subtraction Operation | Medium |
| 0497 | Random Point in Non-overlapping Rectangles | Medium |
| 0528 | Random Pick with Weight | Medium |
| 0902 | Numbers At Most N Given Digit Set | Hard |
| 1201 | Ugly Number III | Medium |
| 1648 | Sell Diminishing-Valued Colored Balls | Medium |
Frequently asked questions
- How hard is LeetCode 2941. Maximum GCD-Sum of a Subarray?
LeetCode 2941. Maximum GCD-Sum of a Subarray is rated Hard on LeetCode.
- What topics does LeetCode 2941. Maximum GCD-Sum of a Subarray cover?
LeetCode 2941. Maximum GCD-Sum of a Subarray is tagged Array, Math, Binary Search and Number Theory on LeetCode.
- Is LeetCode 2941. Maximum GCD-Sum of a Subarray a premium problem?
Yes. LeetCode 2941. Maximum GCD-Sum of a Subarray is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.