LeetCode 3941: Maximize Subarray GCD Score (Prefix GCD Compression)
LeetCode 3941Source: https://leetcode.com/problems/maximize-subarray-gcd-score/
English
Track all distinct GCD values of subarrays ending at each index. When we append nums[i], each previous GCD becomes gcd(prev, nums[i]). Many results collapse to the same value, so we compress by keeping only distinct GCD states with the best subarray length/count information required by the score formula.
Complexity: O(n logV) time, O(logV) states per position.
class Solution {
public long maxGCDScore(int[] nums) {
java.util.List<long[]> states = new java.util.ArrayList<>(); // [gcd, bestLen]
long ans = 0;
for (int x : nums) {
java.util.List<long[]> next = new java.util.ArrayList<>();
next.add(new long[]{x, 1});
for (long[] s : states) {
long g = gcd(s[0], x), len = s[1] + 1;
if (next.get(next.size() - 1)[0] == g) next.get(next.size() - 1)[1] = Math.max(next.get(next.size() - 1)[1], len);
else next.add(new long[]{g, len});
}
for (long[] s : next) ans = Math.max(ans, s[0] * s[1]);
states = next;
}
return ans;
}
private long gcd(long a, long b) { while (b != 0) { long t = a % b; a = b; b = t; } return a; }
}func maxGCDScore(nums []int) int64 {
states := [][2]int64{}
var ans int64
for _, x := range nums {
next := [][2]int64{{int64(x), 1}}
for _, s := range states {
g := gcd(s[0], int64(x))
l := s[1] + 1
if next[len(next)-1][0] == g {
if l > next[len(next)-1][1] { next[len(next)-1][1] = l }
} else { next = append(next, [2]int64{g, l}) }
}
for _, s := range next { if s[0]*s[1] > ans { ans = s[0]*s[1] } }
states = next
}
return ans
}
func gcd(a, b int64) int64 { for b != 0 { a, b = b, a%b }; return a }class Solution {
public:
long long maxGCDScore(vector<int>& nums) {
vector<pair<long long,long long>> states;
long long ans = 0;
for (int x : nums) {
vector<pair<long long,long long>> nxt{{x,1}};
for (auto [g0,l0] : states) {
long long g = std::gcd(g0, (long long)x), l = l0 + 1;
if (nxt.back().first == g) nxt.back().second = max(nxt.back().second, l);
else nxt.push_back({g,l});
}
for (auto [g,l] : nxt) ans = max(ans, g*l);
states.swap(nxt);
}
return ans;
}
};from math import gcd
class Solution:
def maxGCDScore(self, nums: list[int]) -> int:
states: list[tuple[int, int]] = []
ans = 0
for x in nums:
nxt = [(x, 1)]
for g0, l0 in states:
g, l = gcd(g0, x), l0 + 1
if nxt[-1][0] == g:
nxt[-1] = (g, max(nxt[-1][1], l))
else:
nxt.append((g, l))
for g, l in nxt:
ans = max(ans, g * l)
states = nxt
return ansfunction maxGCDScore(nums) {
let states = [];
let ans = 0n;
const gcd = (a, b) => { while (b !== 0n) [a, b] = [b, a % b]; return a; };
for (const x of nums) {
let next = [[BigInt(x), 1n]];
for (const [g0, l0] of states) {
const g = gcd(g0, BigInt(x)), l = l0 + 1n;
if (next[next.length - 1][0] === g) next[next.length - 1][1] = next[next.length - 1][1] > l ? next[next.length - 1][1] : l;
else next.push([g, l]);
}
for (const [g, l] of next) if (g * l > ans) ans = g * l;
states = next;
}
return Number(ans);
}中文
维护“以当前位置结尾”的所有不同 GCD 状态。加入 nums[i] 后，之前每个状态都会变成 gcd(旧值, nums[i])。由于大量状态会合并成相同 GCD，我们只保留去重后的状态，并记录该状态下对分数最优的长度信息，从而在线更新最大分数。
复杂度：时间 O(n logV)，每个位置状态数通常是 O(logV)。
class Solution {
public long maxGCDScore(int[] nums) {
java.util.List<long[]> states = new java.util.ArrayList<>();
long ans = 0;
for (int x : nums) {
java.util.List<long[]> next = new java.util.ArrayList<>();
next.add(new long[]{x, 1});
for (long[] s : states) {
long g = gcd(s[0], x), len = s[1] + 1;
if (next.get(next.size() - 1)[0] == g) next.get(next.size() - 1)[1] = Math.max(next.get(next.size() - 1)[1], len);
else next.add(new long[]{g, len});
}
for (long[] s : next) ans = Math.max(ans, s[0] * s[1]);
states = next;
}
return ans;
}
private long gcd(long a, long b) { while (b != 0) { long t = a % b; a = b; b = t; } return a; }
}func maxGCDScore(nums []int) int64 {
states := [][2]int64{}
var ans int64
for _, x := range nums {
next := [][2]int64{{int64(x), 1}}
for _, s := range states {
g := gcd(s[0], int64(x))
l := s[1] + 1
if next[len(next)-1][0] == g {
if l > next[len(next)-1][1] { next[len(next)-1][1] = l }
} else { next = append(next, [2]int64{g, l}) }
}
for _, s := range next { if s[0]*s[1] > ans { ans = s[0]*s[1] } }
states = next
}
return ans
}
func gcd(a, b int64) int64 { for b != 0 { a, b = b, a%b }; return a }class Solution {
public:
long long maxGCDScore(vector<int>& nums) {
vector<pair<long long,long long>> states;
long long ans = 0;
for (int x : nums) {
vector<pair<long long,long long>> nxt{{x,1}};
for (auto [g0,l0] : states) {
long long g = std::gcd(g0, (long long)x), l = l0 + 1;
if (nxt.back().first == g) nxt.back().second = max(nxt.back().second, l);
else nxt.push_back({g,l});
}
for (auto [g,l] : nxt) ans = max(ans, g*l);
states.swap(nxt);
}
return ans;
}
};from math import gcd
class Solution:
def maxGCDScore(self, nums: list[int]) -> int:
states: list[tuple[int, int]] = []
ans = 0
for x in nums:
nxt = [(x, 1)]
for g0, l0 in states:
g, l = gcd(g0, x), l0 + 1
if nxt[-1][0] == g:
nxt[-1] = (g, max(nxt[-1][1], l))
else:
nxt.append((g, l))
for g, l in nxt:
ans = max(ans, g * l)
states = nxt
return ansfunction maxGCDScore(nums) {
let states = [];
let ans = 0n;
const gcd = (a, b) => { while (b !== 0n) [a, b] = [b, a % b]; return a; };
for (const x of nums) {
let next = [[BigInt(x), 1n]];
for (const [g0, l0] of states) {
const g = gcd(g0, BigInt(x)), l = l0 + 1n;
if (next[next.length - 1][0] === g) next[next.length - 1][1] = next[next.length - 1][1] > l ? next[next.length - 1][1] : l;
else next.push([g, l]);
}
for (const [g, l] of next) if (g * l > ans) ans = g * l;
states = next;
}
return Number(ans);
}
Comments