Maximize Subarray GCD Score
<p>You are given an array of positive integers <code>nums</code> and an integer <code>k</code>.</p>

<p>You may perform at most <code>k</code> operations. In each operation, you can choose one element in the array and <strong>double</strong> its value. Each element can be doubled <strong>at most</strong> once.</p>

<p>The <strong>score</strong> of a contiguous <strong><span data-keyword="subarray">subarray</span></strong> is defined as the <strong>product</strong> of its length and the <em>greatest common divisor (GCD)</em> of all its elements.</p>

<p>Your task is to return the <strong>maximum</strong> <strong>score</strong> that can be achieved by selecting a contiguous subarray from the modified array.</p>

<p><strong>Note:</strong></p>

<ul>
	<li>The <strong>greatest common divisor (GCD)</strong> of an array is the largest integer that evenly divides all the array elements.</li>
</ul>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [2,4], k = 1</span></p>

<p><strong>Output:</strong> <span class="example-io">8</span></p>

<p><strong>Explanation:</strong></p>

<ul>
	<li>Double <code>nums[0]</code> to 4 using one operation. The modified array becomes <code>[4, 4]</code>.</li>
	<li>The GCD of the subarray <code>[4, 4]</code> is 4, and the length is 2.</li>
	<li>Thus, the maximum possible score is <code>2 &times; 4 = 8</code>.</li>
</ul>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [3,5,7], k = 2</span></p>

<p><strong>Output:</strong> <span class="example-io">14</span></p>

<p><strong>Explanation:</strong></p>

<ul>
	<li>Double <code>nums[2]</code> to 14 using one operation. The modified array becomes <code>[3, 5, 14]</code>.</li>
	<li>The GCD of the subarray <code>[14]</code> is 14, and the length is 1.</li>
	<li>Thus, the maximum possible score is <code>1 &times; 14 = 14</code>.</li>
</ul>
</div>

<p><strong class="example">Example 3:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [5,5,5], k = 1</span></p>

<p><strong>Output:</strong> <span class="example-io">15</span></p>

<p><strong>Explanation:</strong></p>

<ul>
	<li>The subarray <code>[5, 5, 5]</code> has a GCD of 5, and its length is 3.</li>
	<li>Since doubling any element doesn&#39;t improve the score, the maximum score is <code>3 &times; 5 = 15</code>.</li>
</ul>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n == nums.length &lt;= 1500</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>
	<li><code>1 &lt;= k &lt;= n</code></li>
</ul>
Array; Math; Enumeration; Number Theory
class Solution {
public:
    long long maxGCDScore(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> cnt(n);
        for (int i = 0; i < n; ++i) {
            for (int x = nums[i]; x % 2 == 0; x /= 2) {
                ++cnt[i];
            }
        }

        long long ans = 0;
        for (int l = 0; l < n; ++l) {
            int g = 0;
            int mi = INT32_MAX;
            int t = 0;
            for (int r = l; r < n; ++r) {
                g = gcd(g, nums[r]);
                if (cnt[r] < mi) {
                    mi = cnt[r];
                    t = 1;
                } else if (cnt[r] == mi) {
                    ++t;
                }
                long long score = static_cast<long long>(r - l + 1) * (t > k ? g : g * 2);
                ans = max(ans, score);
            }
        }

        return ans;
    }
};
