2941. Maximum GCD-Sum of a Subarray

Try to answer the query of asking GCD of a subarray in O(1) using sparse tables and preprocessing.

For every index L, let’s find the subarray starting at the index L and maximizing gcd-sum.

Use the fact that if L is fixed, then by adding one more element to the end of a subarray, two things can happen: the gcd remains the same as the last gcd or becomes at least half of the last one.

Now we can use binary search to find the last index R such that gcd of the elements of nums[L..R] would be equal to nums[L].

Now add nums[R + 1] to the current subarray and continue the process to find the last index that has the same gcd as the current gcd of elements.