Description#
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. - Let
g be the greatest common divisor of all the elements of a. - The gcd-sum of
a is equal to s * g.
Return the maximum gcd-sum of a subarray of nums with at least k elements.
Example 1:
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.
It can be shown that we can not select any other subarray with a gcd-sum greater than 48.
Example 2:
Input: nums = [7,3,9,4], k = 1
Output: 81
Explanation: We take the subarray [9], the gcd-sum of this array is 9 * 9 = 81.
It can be shown that we can not select any other subarray with a gcd-sum greater than 81.
Constraints:
n == nums.length1 <= n <= 1051 <= nums[i] <= 1061 <= k <= n
Solutions#
Solution 1#
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:
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 ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| class Solution {
public long maxGcdSum(int[] nums, int k) {
int n = nums.length;
long[] s = new long[n + 1];
for (int i = 1; i <= n; ++i) {
s[i] = s[i - 1] + nums[i - 1];
}
List<int[]> f = new ArrayList<>();
long ans = 0;
for (int i = 0; i < n; ++i) {
List<int[]> g = new ArrayList<>();
for (var e : f) {
int j = e[0], x = e[1];
int y = gcd(x, nums[i]);
if (g.isEmpty() || g.get(g.size() - 1)[1] != y) {
g.add(new int[] {j, y});
}
}
f = g;
f.add(new int[] {i, nums[i]});
for (var e : f) {
int j = e[0], x = e[1];
if (i - j + 1 >= k) {
ans = Math.max(ans, (s[i + 1] - s[j]) * x);
}
}
}
return ans;
}
private int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| class Solution {
public:
long long maxGcdSum(vector<int>& nums, int k) {
int n = nums.size();
long long s[n + 1];
s[0] = 0;
for (int i = 1; i <= n; ++i) {
s[i] = s[i - 1] + nums[i - 1];
}
vector<pair<int, int>> f;
long long ans = 0;
for (int i = 0; i < n; ++i) {
vector<pair<int, int>> g;
for (auto [j, x] : f) {
int y = gcd(x, nums[i]);
if (g.empt() || g.back().second != y) {
g.emplace_back(j, y);
}
}
f = move(g);
f.emplace_back(i, nums[i]);
for (auto [j, x] : f) {
if (i - j + 1 >= k) {
ans = max(ans, (s[i + 1] - s[j]) * x);
}
}
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| func maxGcdSum(nums []int, k int) int64 {
n := len(nums)
s := make([]int64, n+1)
s[0] = 0
for i, x := range nums {
s[i+1] = s[i] + int64(x)
}
type pair [2]int
var f []pair
var ans int64
for i := 0; i < n; i++ {
var g []pair
for _, p := range f {
j, x := p[0], p[1]
y := int(gcd(int(x), nums[i]))
if len(g) == 0 || g[len(g)-1][1] != y {
g = append(g, pair{j, y})
}
}
f = g
f = append(f, pair{i, nums[i]})
for _, p := range f {
j, x := p[0], p[1]
if i-j+1 >= k {
ans = max(ans, (s[i+1]-s[j])*int64(x))
}
}
}
return ans
}
func gcd(a, b int) int {
if b == 0 {
return a
}
return gcd(b, a%b)
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| function maxGcdSum(nums: number[], k: number): number {
const n: number = nums.length;
const s: number[] = Array(n + 1).fill(0);
for (let i = 1; i <= n; i++) {
s[i] = s[i - 1] + nums[i - 1];
}
let f: [number, number][] = [];
let ans: number = 0;
for (let i = 0; i < n; ++i) {
const g: [number, number][] = [];
for (const [j, x] of f) {
const y: number = gcd(x, nums[i]);
if (g.length === 0 || g.at(-1)[1] !== y) {
g.push([j, y]);
}
}
f = g;
f.push([i, nums[i]]);
for (const [j, x] of f) {
if (i - j + 1 >= k) {
ans = Math.max(ans, (s[i + 1] - s[j]) * x);
}
}
}
return ans;
}
function gcd(a: number, b: number): number {
return b === 0 ? a : gcd(b, a % b);
}
|
Solution 2#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| function maxGcdSum(nums: number[], k: number): number {
const n: number = nums.length;
const s: number[] = Array(n + 1).fill(0);
for (let i = 1; i <= n; i++) {
s[i] = s[i - 1] + nums[i - 1];
}
let f: [number, number][] = [];
let ans: number = 0;
for (let i = 0; i < n; ++i) {
const g: [number, number][] = [];
for (const [j, x] of f) {
const y: number = gcd(x, nums[i]);
if (g.length === 0 || g.at(-1)[1] !== y) {
g.push([j, y]);
}
}
f = g;
f.push([i, nums[i]]);
for (const [j, x] of f) {
if (i - j + 1 >= k) {
ans = Math.max(ans, (s[i + 1] - s[j]) * x);
}
}
}
return ans;
}
function gcd(a: number, b: number): number {
return b === 0 ? a : gcd(b, a % b);
}
|
