n 個の整数からなる数列 a₁ … aₙ が与えられる。
この数列からいくつかを選んで（元の順番はそのまま、間を飛ばしてもよい）作った数列が狭義に増加する（後ろの数がいつも前の数より大きい、等しいのはだめ）とき、そのような数列の最大の長さを出力せよ。
一つだけ選んだ数列も増加する数列とみなす。
たとえば 3 1 4 1 5 9 2 6 では 1 4 5 9（または 3 4 5 6 など）を選べて、長さ 4 が最長である。
一行目に n、二行目に a₁ … aₙ が空白区切りで与えられる。
8 3 1 4 1 5 9 2 6
4
5 2 2 2 2 2
1
実行すると、これらの行が順に input()・標準入力に渡されます(実行中に入力を求めません)。
$ 準備完了
コードを入力して解くにはパソコンで開いてください。モバイルでは問題と解答を見られます。
length[i] を「a[i] で終わる最長の増加列の長さ」とすると、前の j < i のうち a[j] < a[i] であるものの length[j] + 1 の最大値です（なければ 1）。
二重ループは n²/2 = 約 200 万回なので 8 言語とも余裕です（Craykon の実行ステップ上限 約 5 千万の範囲内）。
罠は三つ：等しい値もつなぐ <= は「狭義増加」ではありません。
答えは最後のマス length[n-1] ではなく全マスの最大値です — 最長の列が最後で終わるとは限りません。
そして連続した区間だけを数えると、間を飛ばす列を見落とします。
最大値の求め方は言語ごとに違います：Python max(length)、C# LINQ length.Max()、C++ *std::max_element(…)、JavaScript・TypeScript Math.max(...length)（展開する引数の数に上限があるので数十万を超えるならループが安全）。
Java と C は best を別に持ちます（Java は Arrays.stream(length).max().getAsInt() も可）。
初期値の埋め方も違います：Python [1] * n、JS new Array(n).fill(1)、C++ vector<int>(n, 1)、Java・C#・C は 0 で埋まるので length[i] = 1 を自分で書きます。
Craykon は 新リスト(n, 1) で作り、best を別に持ちます。
import sys data = sys.stdin.read().split()n = int(data[0])a = list(map(int, data[1:1 + n])) # length[i] = a[i]로 끝나는 가장 긴 증가 부분 수열의 길이length = [1] * nfor i in range(n): for j in range(i): if a[j] < a[i] and length[j] + 1 > length[i]: length[i] = length[j] + 1print(max(length))const [n, ...a] = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number); // length[i] = a[i]로 끝나는 가장 긴 증가 부분 수열의 길이const length = new Array(n).fill(1);for (let i = 0; i < n; i++) { for (let j = 0; j < i; j++) { if (a[j] < a[i] && length[j] + 1 > length[i]) length[i] = length[j] + 1; }}console.log(Math.max(...length));import { readFileSync } from "node:fs";const [n, ...a]: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number); // length[i] = a[i]로 끝나는 가장 긴 증가 부분 수열의 길이const length: number[] = new Array(n).fill(1);for (let i = 0; i < n; i++) { for (let j = 0; j < i; j++) { if (a[j] < a[i] && length[j] + 1 > length[i]) length[i] = length[j] + 1; }}console.log(Math.max(...length));import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine().trim()); StringTokenizer st = new StringTokenizer(br.readLine()); int[] a = new int[n]; for (int i = 0; i < n; i++) a[i] = Integer.parseInt(st.nextToken()); // length[i] = a[i]로 끝나는 가장 긴 증가 부분 수열의 길이 int[] length = new int[n]; int best = 0; for (int i = 0; i < n; i++) { length[i] = 1; for (int j = 0; j < i; j++) { if (a[j] < a[i] && length[j] + 1 > length[i]) length[i] = length[j] + 1; } best = Math.max(best, length[i]); } System.out.println(best); }}using System;using System.Linq; class Program{ static void Main() { int n = int.Parse(Console.ReadLine()); int[] a = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries).Select(int.Parse).ToArray(); // length[i] = a[i]로 끝나는 가장 긴 증가 부분 수열의 길이 int[] length = new int[n]; for (int i = 0; i < n; i++) { length[i] = 1; for (int j = 0; j < i; j++) { if (a[j] < a[i] && length[j] + 1 > length[i]) length[i] = length[j] + 1; } } Console.WriteLine(length.Max()); }}#include <algorithm>#include <iostream>#include <vector> int main() { int n; std::cin >> n; std::vector<int> a(n); for (int& x : a) std::cin >> x; // length[i] = a[i]로 끝나는 가장 긴 증가 부분 수열의 길이 std::vector<int> length(n, 1); for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { if (a[j] < a[i] && length[j] + 1 > length[i]) length[i] = length[j] + 1; } } std::cout << *std::max_element(length.begin(), length.end()) << '\n';}#include <stdio.h> #define MAXN 2000 int main(void) { static int a[MAXN], length[MAXN]; int n; scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", &a[i]); /* length[i] = a[i]로 끝나는 가장 긴 증가 부분 수열의 길이 */ int best = 0; for (int i = 0; i < n; i++) { length[i] = 1; for (int j = 0; j < i; j++) { if (a[j] < a[i] && length[j] + 1 > length[i]) length[i] = length[j] + 1; } if (length[i] > best) best = length[i]; } printf("%d\n", best); return 0;}n = コンソール.行読み().数に();a = コンソール.数読み();// len[i] = a[i]로 끝나는 가장 긴 증가 부분 수열의 길이len = 新リスト(n, 1);best = 1;繰り返す (i = 1; i < n; i++){ 繰り返す (j = 0; j < i; j++) { もし (a[j] < a[i] && len[j] + 1 > len[i]) { len[i] = len[j] + 1; } } もし (len[i] > best) { best = len[i]; }}コンソール.書く(best);