Find the Maximum Value in a std::map

std::map is ordered by keys, not by values. To find the element with the maximum value, use std::max_element.

Code

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 << ")\n";

Bonus: Maximum Key

Since std::map is sorted by key:

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

Tip: Counting Distinct Elements in All Prefixes

When a problem asks for the number of distinct elements before or up to each index, use prefix traversal + frequency tracking.

Idea

• Traverse the array from left to right.
• Maintain a frequency map (or array).
• When an element appears for the first time, increase the distinct count.
• Store this count for each prefix.

Implementation

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

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

Sum of Distinct Counts Over All Prefixes

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

Why This Works

Each element contributes to the distinct count exactly once, at its first occurrence.