【每日一算法】所有元素的 最大值 和 最大公约数 相等

题目描述

Silencer76 定义一个序列是 好序列 ，当且仅当序列中所有元素的 最大值 和 最大公约数 相等。
给定一个长度为 n 的正整数序列 a ，请找出最长的符合好序列定义的子序列，输出它的长度。

输入描述:

输出描述:

示例一

输入

5
1 2 3 2 1

输出

2

示例说明：

根据题意，子序列中的元素的最大值和最大公约数要相等，其实我们根据示例不难看出，只有当两个数相等时，他的最大值和最大公约数才相等，如示例一中 1 2 3 2 1 ，1与1的最大值为1，最大公约数也为1，所以示例一中符合的子序列为 1 1  和 2 2  和 3 ，最长的子序列长度便为 2 。

思路：

所以本题的要求便是找出给定序列中最多的相同元素的个数。

我们可以先给所给序列排序，目的是为了将相同的元素放在一起，方便后面计数相同元素的个数。

代码如下：

#include<iostream>
#include<algorithm>
using namespace std;

int main(){
    int n;
    int maxn = 0;
    int count = 1;
    cin>>n;
    
    int arr[n] = {0};
    for( int i = 0 ; i < n ; i++){
        cin>>arr[i];
    }
    sort( arr , arr + n );
    for( int i = 1 ; i < n ; i++ ){
        if( arr[i-1] == arr[i] ){
            count++;
        }else{
            maxn = max( maxn , count );
            count = 1;
            
        }
    }
    maxn = max( maxn , count );//注意在循环结束后要再判断一次，以免落下最后符合条件的子序列
    cout<<maxn;
    return 0;
    
}