Package g1701_1800.s1799_maximize_score_after_n_operations

Class Solution

java.lang.Object
g1701_1800.s1799_maximize_score_after_n_operations.Solution
public class Solution extends Object
1799 - Maximize Score After N Operations.<p>Hard</p> <p>You are given <code>nums</code>, an array of positive integers of size <code>2 * n</code>. You must perform <code>n</code> operations on this array.</p> <p>In the <code>i<sup>th</sup></code> operation <strong>(1-indexed)</strong> , you will:</p> <ul> <li>Choose two elements, <code>x</code> and <code>y</code>.</li> <li>Receive a score of <code>i * gcd(x, y)</code>.</li> <li>Remove <code>x</code> and <code>y</code> from <code>nums</code>.</li> </ul> <p>Return <em>the maximum score you can receive after performing</em> <code>n</code> <em>operations.</em></p> <p>The function <code>gcd(x, y)</code> is the greatest common divisor of <code>x</code> and <code>y</code>.</p> <p><strong>Example 1:</strong></p> <p><strong>Input:</strong> nums = [1,2]</p> <p><strong>Output:</strong> 1</p> <p><strong>Explanation:</strong> The optimal choice of operations is:</p> <p>v(1 * gcd(1, 2)) = 1</p> <p><strong>Example 2:</strong></p> <p><strong>Input:</strong> nums = [3,4,6,8]</p> <p><strong>Output:</strong> 11</p> <p><strong>Explanation:</strong> The optimal choice of operations is:</p> <p>(1 * gcd(3, 6)) + (2 * gcd(4, 8)) = 3 + 8 = 11</p> <p><strong>Example 3:</strong></p> <p><strong>Input:</strong> nums = [1,2,3,4,5,6]</p> <p><strong>Output:</strong> 14</p> <p><strong>Explanation:</strong> The optimal choice of operations is:</p> <p>(1 * gcd(1, 5)) + (2 * gcd(2, 4)) + (3 * gcd(3, 6)) = 1 + 4 + 9 = 14</p> <p><strong>Constraints:</strong></p> <ul> <li><code>1 <= n <= 7</code></li> <li><code>nums.length == 2 * n</code></li> <li><code>1 <= nums[i] <= 10<sup>6</sup></code></li> </ul>

  • Constructor Details

    • Solution

      public Solution()

  • Method Details

    • maxScore

      public int maxScore(int[] nums)