1차 시도

문제에서 주어진 대로 코드를 작성했습니다.

전체 배열을 반으로 나누고 왼쪽 부분의 최대공약수를 구한 뒤 재귀적으로 오른쪽 부분의 아름다움을 구했습니다.

오른쪽 부분도 같은 방법으로 구하면 됩니다.

각 재귀 단계에서 왼쪽과 오른쪽 부분의 최대공약수를 모두 구하므로 시간 복잡도는 $O(N)$이며 재귀 단계마다 $N$의 크기가 반으로 줄기 때문에 총 시간 복잡도는 $O(N\log{N})$입니다.

2차 시도

1차 시도에서는 왼쪽 부분의 최대공약수를 구한 뒤 마지막으로 왼쪽 부분의 아름다움을 재귀적으로 구하는 과정에서 왼쪽 부분의 최대공약수를 다시 구하게 됩니다.

재귀 단계마다 아름다움과 함께 전체 범위의 최대공약수를 반환하도록 하면 이 문제를 해결할 수 있습니다.

마지막 재귀 단계에서 전체 배열을 한 번 순회하고, 각 단계마다 결과를 합치는 연산만 일어나므로 시간 복잡도는 $O(N)$입니다.

코드 
fn gcd(mut a: u32, mut b: u32) -> u32 {
    while b > 0 {
        let c = a % b;
        a = b;
        b = c;
    }
    a
}

fn solve(num: &[u32]) -> (u32, u32) {
    let len = num.len();
    if len == 1 {
        (num[0], num[0])
    } else {
        let half = len >> 1;
        let (left, right) = num.split_at(half);
        let (left_gcd, left_sum) = solve(left);
        let (right_gcd, right_sum) = solve(right);
        let gcd = gcd(left_gcd, right_gcd);
        let sum = std::cmp::max(left_gcd + right_sum, right_gcd + left_sum);
        (gcd, sum)
    }
}