# Lời giải bài Giá trị lớn nhất
###### 📌 Tags: `Counting sort` .
____
## Ý tưởng :+1:
* Đếm số lần xuất hiện của 1 giá trị . Ta sẽ có 1 tập số xuất hiện một lần việc cần làm là tìm giá trị lớn nhất trong tập số đó . Để làm được điều đó ta cần phải tạo ra một mảng đếm số lần xuất hiện của từng giá trị. $cnt[X]$ quản lý số lần xuất hiện của giá trị $X$.
>[color=lightgreen]
:::success
$cnt[a[i]] += 1$ nếu a[i] xuất hiện một 1 lần trong mảng khi ta duyệt i từ 1 -> n
* Việc đơn giản bây giờ là với từng a[i] ta nếu $cnt[a[i]] == 1$ thì số đó xuất hiện duy nhất 1 lần với mỗi lần tìm ra a[i] như vậy ta so sánh tìm giá trị max lớn nhất

:::::
* Ý tưởng không dùng đếm phân phối :
>[color=lightgreen]
:::success
Sắp xếp lại tăng dần và chạy ngược từ n về 1
với $a[n]$ nếu $a[n - 1] == a[n]$ thì số $a[n]$ không xuất hiện 1 lần
với $a[1]$ nếu $a[1] == a[2]$ thì số $a[1]$ không xuất hiện 1 lần
còn lại với $a[i]$ $(2 \le i \le n - 1)$ nếu $a[i] \neq a[i - 1]$ và $a[i] \neq a[i + 1]$ thì $a[i]$ đó xuất hiện 1 lần lập tức in ra vì đã sort còn chạy ngược nên $a[i]$ lớn nhất.
:::::

____
## Nhận xét :bulb:
+ dùng mảng bình thường thì quá bộ nhớ dùng [map](https://codelearn.io/sharing/cau-truc-du-lieu-than-thanh-mang-ten-map) thì mới là chân lý !!!
+ Tham khảo thêm ở [đây](https://www.stdio.vn/modern-cpp/stl-map-trong-c-v12lmL)
____
## Code
> **Time:** $O(nlogn)$
> **Space:** $O(n)$
> **Algo:** Counting sort.
> [color=lightgreen]
:::success
:::spoiler code

 #include <bits/stdc++.h>
using namespace std;
#define ll long long
ll GCD(ll a1 , ll b1){
   while(b1 != 0){
       a1 = a1 % b1;
       ll tmp = b1;
       b1 = a1;
       a1 = tmp;
   }
   return a1;
}
 
const ll INF = 1e18 + 7;
const ll MAXN = 1e6 + 7;
ll a[MAXN];
int n ;
map<ll ,int > cnt;
int main(){
   freopen("VALUEMAX.inp" , "r" , stdin);
   freopen("VALUEMAX.out" , "w" , stdout);
   cin>> n;
   for(int i = 1 ; i <= n ; i ++){
    cin >> a[i];
    cnt[a[i]] ++;
   }
   ll res = -INF;
   for(int i = 1 ; i <= n ; i ++){
       if(cnt[a[i]] == 1){
               res = max(res , a[i]);
       }
   }
   cout << res;
   return 0;
}

:::success
:::::