This proof is not very rigorous but I hope it gives some intuition. So the first thing is to realize that the highest (let’s call its value max) and the second highest unique elements cannot be in the same subsequence. Let’s say they were in the same subsequence, then the GCD of the group containing both of them can be at most the max / 2. This is because the prime factorization of the highest element might look p1 * p2 * … pk, and the GCD of the subsequence would be maximized if the second highest contained all these primes p1…pk except the smallest one (they have to be unique). In the best case that prime is 2.

Now, in the best case the other subsequence just has one element, the third highest, but since that is less than the second highest it can also only be max / 2. So overall the total can only be max, but in that case we are just better off putting the max alone in one subsequence, and the other subsequence will have gcd at least 1, which will give us max + 1.

By the same logic, we can also see that both subsequences cannot have more than 1 unique element, because if they did the highest gcd for both would be max / 2, which only yields a total of max. So, you see which one is better, putting the highest separately or the second highest and then output your solution.