Sponsored
Sponsored
This approach uses backtracking to explore all possible pairs of elements for the operations. The goal is to maximize the sum of scores obtained from each operation. To optimize the solution, pruning is applied by avoiding redundant calculations using a memoization table. By systematically trying all combinations, we gradually eliminate suboptimal solutions and select the maximal score possible.
Time Complexity: O((2n)! / 2^n), the approach explores all possible combinations of pairs.
Space Complexity: O(2^n), for memoization array to store intermediate results.
1using System;
2
3public class MaxScore {
4 static int GCD(int a, int b) {
5 while (b != 0) {
6 int temp = b;
7 b = a % b;
8 a = temp;
9 }
10 return a;
11 }
12
13 static void Backtrack(int[] nums, int n, int used, int currentScore, ref int maxScore, int[] memo) {
14 if (used == (1 << n) - 1) {
15 maxScore = Math.Max(maxScore, currentScore);
16 return;
17 }
18 if (memo[used] >= currentScore) {
19 return;
20 }
21 memo[used] = currentScore;
22
23 for (int i = 0; i < n; ++i) {
24 if ((used & (1 << i)) == 0) {
25 for (int j = i + 1; j < n; ++j) {
26 if ((used & (1 << j)) == 0) {
27 int pairScore = GCD(nums[i], nums[j]) * ((BitCount(used) / 2) + 1);
28 Backtrack(nums, n, used | (1 << i) | (1 << j), currentScore + pairScore, ref maxScore, memo);
29 }
30 }
31 }
32 }
33 }
34
35 static int BitCount(int number) {
36 int count = 0;
37 while (number != 0) {
38 count += number & 1;
39 number >>= 1;
40 }
41 return count;
42 }
43
44 public static int MaxScore(int[] nums) {
45 int n = nums.Length / 2;
46 int maxScore = 0;
47 int[] memo = new int[1 << nums.Length];
48 Backtrack(nums, n, 0, 0, ref maxScore, memo);
49 return maxScore;
50 }
51
52 public static void Main() {
53 int[] nums = {1, 2, 3, 4, 5, 6};
54 Console.WriteLine("Max Score: " + MaxScore(nums));
55 }
56}The C# solution uses recursive backtracking with bit manipulation. Memoization is leveraged through internal array tracking.
This approach leverages dynamic programming along with bit masking to compute the maximum score possible. The idea is to use a DP state to remember the best score possible with a certain combination of pairs already taken. The state is determined by a bitmask which indicates the taken pairs. Recursively calculate the maximum possible score, storing intermediate results to avoid repeated calculations.
Time Complexity: O(n^2 * 2^n), where n is the number of elements in 'nums'.
Space Complexity: O(2^n) for the DP array.
public class MaxScore {
public static int GCD(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
public static int MaxScore(int[] nums) {
int n = nums.Length / 2;
int[] dp = new int[1 << nums.Length];
Array.Fill(dp, int.MinValue);
dp[0] = 0;
for (int mask = 0; mask < (1 << nums.Length); ++mask) {
int ops = BitCount(mask) / 2 + 1;
for (int i = 0; i < nums.Length; ++i) {
if ((mask & (1 << i)) == 0) {
for (int j = i + 1; j < nums.Length; ++j) {
if ((mask & (1 << j)) == 0) {
int new_mask = mask | (1 << i) | (1 << j);
dp[new_mask] = Math.Max(dp[new_mask], dp[mask] + ops * GCD(nums[i], nums[j]));
}
}
}
}
}
return dp[(1 << nums.Length) - 1];
}
public static int BitCount(int n) {
int count = 0;
while (n != 0) {
count += n & 1;
n >>= 1;
}
return count;
}
public static void Main() {
int[] nums = {1, 2, 3, 4, 5, 6};
Console.WriteLine("Max Score: " + MaxScore(nums));
}
}C# employs DP using bitmasking to store and update scores for different sets of paired selections, aiming to capture the maximal achievable score.