060.md

060 - Chimera (★5)

解答

#include <iostream>
#include <vector>
#include <algorithm> // std::lower_bound(), std::upper_bound(), std::max()

// 最長増加部分列 (LIS) を計算する関数
template <bool Strong = true> // Strong: 狭義単調増加を選ぶ場合 true
int LIS(const std::vector<int>& v, std::vector<size_t>& counts)
{
	std::vector<int> dp;

	auto it = dp.begin();

	for (const auto& elem : v)
	{
		if constexpr (Strong)
		{
			it = std::lower_bound(dp.begin(), dp.end(), elem);
		}
		else
		{
			it = std::upper_bound(dp.begin(), dp.end(), elem);
		}

		if (it == dp.end())
		{
			dp.push_back(elem);
		}
		else
		{
			*it = elem;
		}

		// ここまでの LIS の長さを記録
		counts.push_back(dp.size());
	}

	return dp.size();
}

int main()
{
	// 長さ N の数列
	int N;
	std::cin >> N;

	std::vector<int> A(N);
	for (auto& a : A)
	{
		std::cin >> a;
	}
	// A の逆順
	std::vector<int> B(A.rbegin(), A.rend());

	// 各要素までの LIS の長さを記録する配列
	std::vector<size_t> countsA, countsB;
	
	LIS(A, countsA);
	
	LIS(B, countsB);

	size_t answer = 0;

	// ((A の LIS の長さ) + (B の LIS の長さ) - 1) で, 最も大きくなる値を探す
	for (int i = 0; i < N; ++i)
	{
		answer = std::max(answer, (countsA[i] + countsB[N - i - 1] - 1));
	}

	std::cout << answer << '\n';
}