# sum and gcd june19 challenge!

Chef has a sequence of positive integers $$A_1,A_2, \dots, A_N$$. He wants to split this sequence into two non-empty (not necessarily contiguous) subsequences $$B$$ and $$C$$ such that $$\text{GCD}(B) + \text{GCD}(C)$$ is maximum possible. Help him find this maximum value.

Example case 1: For example, the sequence $$A=(4,4,7,6)$$ can be divided into subsequences $$B=(4,4,6)$$ and $$C=(7)$$.

But how the output comes out to be 9 As gcd of 7 is 1 itself.

• Is the question here to do with how the example case works? Jun 22 '19 at 20:22
• In that case, GCD of a single integer is the integer itself, thus $GCD(7)=7$ ... Jun 22 '19 at 22:38
• @athin has it right. Note that the definition of GCD given is "the largest positive integer that divides each element of this sequence," which does not necessarily imply the output is smaller than the inputs. Jun 23 '19 at 14:44

Example case 1:** For example, the sequence $$A=(4,4,7,6)$$ can be divided into subsequences $$B=(4,4,6)$$ and $$C=(7)$$.

GCD(B) = 2
GCD(C) = 7
GCD(B) + GCD(C) = 2 + 7 = 9