Find the Max Value in a std::map

Since std::map is sorted by keys, not values, you can use std::max_element to find the pair with the largest value:

auto it = max_element(
    m.begin(), m.end(),
    [](const auto &a, const auto &b) {
        return a.second < b.second;
    }
);

cout << "Max value: " << it->second << " (Key: " << it->first << ")" << endl;

Explanation:

• std::max_element iterates through all pairs.
• The lambda compares elements based on their second value.
• The iterator it points to the pair with the maximum value.

Bonus

If you want the maximum key instead, you can write:

auto last = m.rbegin();
cout << last->first << " " << last->second;

Tip: Counting Distinct Elements in All Prefixes

When a problem asks you to count distinct numbers before (or up to) each index, think in terms of prefix processing + frequency tracking.

Idea: Stand at each index i and maintain a frequency array (or map).

If the current element appears for the first time, then the number of distinct elements increases by one.

Store this count as the number of distinct elements in the prefix ending at i.

Implementation Sketch:

map<int, int> freq; vector distinct(n); int cnt = 0;

for (int i = 0; i < n; i++) { freq[x[i]]++; if (freq[x[i]] == 1) { cnt++; // new distinct element } distinct[i] = cnt; // distinct elements up to index i }

If the problem later asks for the sum of distinct counts over all prefixes, simply accumulate:

long long ans = 0; for (int i = 0; i < n; i++) { ans += distinct[i]; }

Why this works: Each element contributes to the distinct count only once, exactly at its first occurrence.