3574. Maximize Subarray GCD Score Hard

1/**
2 * [3574] Maximize Subarray GCD Score
3 *
4 * You are given an array of positive integers nums and an integer k.
5 * You may perform at most k operations. In each operation, you can choose one element in the array and double its value. Each element can be doubled at most once.
6 * The score of a contiguous <span data-keyword="subarray">subarray</span> is defined as the product of its length and the greatest common divisor (GCD) of all its elements.
7 * Your task is to return the maximum score that can be achieved by selecting a contiguous subarray from the modified array.
8 * Note:
9 * 
10 * 	The greatest common divisor (GCD) of an array is the largest integer that evenly divides all the array elements.
11 * 
12 *  
13 * <strong class="example">Example 1:
14 * <div class="example-block">
15 * Input: <span class="example-io">nums = [2,4], k = 1</span>
16 * Output: <span class="example-io">8</span>
17 * Explanation:
18 * 
19 * 	Double nums[0] to 4 using one operation. The modified array becomes [4, 4].
20 * 	The GCD of the subarray [4, 4] is 4, and the length is 2.
21 * 	Thus, the maximum possible score is 2 &times; 4 = 8.
22 * </div>
23 * <strong class="example">Example 2:
24 * <div class="example-block">
25 * Input: <span class="example-io">nums = [3,5,7], k = 2</span>
26 * Output: <span class="example-io">14</span>
27 * Explanation:
28 * 
29 * 	Double nums[2] to 14 using one operation. The modified array becomes [3, 5, 14].
30 * 	The GCD of the subarray [14] is 14, and the length is 1.
31 * 	Thus, the maximum possible score is 1 &times; 14 = 14.
32 * </div>
33 * <strong class="example">Example 3:
34 * <div class="example-block">
35 * Input: <span class="example-io">nums = [5,5,5], k = 1</span>
36 * Output: <span class="example-io">15</span>
37 * Explanation:
38 * 
39 * 	The subarray [5, 5, 5] has a GCD of 5, and its length is 3.
40 * 	Since doubling any element doesn't improve the score, the maximum score is 3 &times; 5 = 15.
41 * </div>
42 *  
43 * Constraints:
44 * 
45 * 	1 <= n == nums.length <= 1500
46 * 	1 <= nums[i] <= 10^9
47 * 	1 <= k <= n
48 * 
49 */
50pub struct Solution {}
51
52// problem: https://leetcode.com/problems/maximize-subarray-gcd-score/
53// discuss: https://leetcode.com/problems/maximize-subarray-gcd-score/discuss/?currentPage=1&orderBy=most_votes&query=
54
55// submission codes start here
56
57impl Solution {
58    pub fn max_gcd_score(nums: Vec<i32>, k: i32) -> i64 {
59        
60    }
61}
62
63// submission codes end
64
65#[cfg(test)]
66mod tests {
67    use super::*;
68
69    #[test]
70    fn test_3574() {
71    }
72}
73