You are given a sequence of n integers a₁ … aₙ. Choose some of them (keeping their original order; you may skip elements in between) so that the chosen sequence is strictly increasing (each number is greater than the one before it; equal is not allowed). Print the greatest possible length of such a sequence. A single chosen number counts as an increasing sequence. For example, in 3 1 4 1 5 9 2 6 you can choose 1 4 5 9 (or 3 4 5 6, etc.), so the longest length is 4.
The first line gives n, and the second line gives a₁ … aₙ separated by spaces.
Input
1 ≤ n ≤ 2,000, -10⁹ ≤ aᵢ ≤ 10⁹
Output
The length of the longest strictly increasing subsequence (one integer)
Example 1 · stdin
8
3 1 4 1 5 9 2 6
stdout
4
Example 2 · stdin
5
2 2 2 2 2
stdout
1
main.py
Error List00F8 ↓ · ⇧F8 ↑
Input (stdin)
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
Let length[i] be 'the length of the longest increasing sequence ending at a[i]': it is the largest length[j] + 1 over earlier j < i with a[j] < a[i] (or 1 if there is none). The double loop runs about n²/2 = 2 million times, which is comfortable in all 8 languages (well under Craykon's limit of about 50 million execution steps). Three traps: <= also chains equal values, which is not 'strictly increasing'. The answer is not the last cell length[n-1] but the largest value over all cells — the longest sequence need not end at the last element. And counting only contiguous runs misses sequences that skip elements. Taking the maximum differs by language: Python max(length), C# LINQ length.Max(), C++ *std::max_element(…), JavaScript/TypeScript Math.max(...length) (spread arguments have a size limit, so a loop is safer beyond a few hundred thousand cells). Java and C carry a separate best (Java can also use Arrays.stream(length).max().getAsInt()). Initial filling differs too: Python [1] * n, JS new Array(n).fill(1), C++ vector<int>(n, 1); Java, C# and C fill with 0, so you write length[i] = 1 yourself. Craykon builds the list with NewList(n, 1) and carries a separate best.
Pythonmain.py · 13 lines
import sysdata = 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))
JavaScriptmain.js · 10 lines
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));
TypeScriptmain.ts · 11 lines
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));
JavaMain.java · 26 lines
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); }}
C#Main.cs · 23 lines
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()); }}
C++main.cpp · 19 lines
#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';}
Cmain.c · 22 lines
#include <stdio.h>#define MAXN 2000int 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;}
Craykonmain.cray · 20 lines
n = Console.ReadLine().ToNumber();a = Console.ReadNumbers();// len[i] = a[i]로 끝나는 가장 긴 증가 부분 수열의 길이len = NewList(n, 1);best = 1;for (i = 1; i < n; i++){ for (j = 0; j < i; j++) { if (a[j] < a[i] && len[j] + 1 > len[i]) { len[i] = len[j] + 1; } } if (len[i] > best) { best = len[i]; }}Console.WriteLine(best);