CSAcademy Subarray Partition

csacademy.com

＜問題＞
長さの配列が与えられる。
を、同じ数は全て１つの連続する部分列に含まれるように分けるとき、最大でいくつに分割できるか。
(たとえば5がの 5,9, 12番目に含まれるとすると少なくとも5~12番目を１つの部分列に含める必要がある。)

＜解説＞
事前にmap[ ]での現れる最大のindexを指すようにmapを構築します。
を調べながら、それまで出てきた最大のmap[ ]を持ち、
になれば(現在までの数が全て含まれている)答えを１インクリメントしていきます。

＜コード＞

int main() {

	int n;
	cin >> n;
	vi a(n);
	rep(i, n)cin >> a[i];

	map<int, int> m;
	rep(i, n) {
		m[a[i]] = i;
	}

	int ans = 0;

	int max_i = 0;

	rep(i, n) {
		max_i = max(max_i,m[a[i]]);
		if (i == max_i) {
			ans++;
		}
	}
	P(ans);
	return 0;
}

＜感想＞
問題文と公式解説（こっちは理解していない）が難しかった。