trang chủ / đề bài / consecsub

Dãy con các số nguyên liên tiếp

Đề bài

Mô tả

Cho một dãy số nguyên a1,a2,…,an.

Hãy chọn ra một dãy con có độ dài lớn nhất sao cho dãy con đó là một dãy các số nguyên liên tiếp tăng dần, tức là dãy con đó phải có dạng [x,x+1,…,x+k−1] với một giá trị x và độ dài k nào đó.

Dãy con của một dãy thu được bằng cách xoá đi một số (có thể bằng 0) phần tử; các phần tử còn lại giữ nguyên thứ tự ban đầu. Ví dụ với dãy [5,3,1,2,4] thì [3], [5,3,1,2,4], [5,1,4] đều là dãy con, còn [1,3] thì không.

Nếu có nhiều đáp án cùng đạt độ dài lớn nhất, in ra đáp án nào cũng được.

Dữ liệu vào

  • Dòng đầu chứa số nguyên n là độ dài của dãy.
  • Dòng thứ hai chứa n số nguyên a1,a2,…,an.

Dữ liệu ra

  • Dòng đầu in ra k là độ dài lớn nhất của dãy con thoả mãn.
  • Dòng thứ hai in ra k chỉ số (tăng dần) của các phần tử tạo thành dãy con đó. Các chỉ số được đánh số từ 1.

Ràng buộc

  • 1≤n≤2·105
  • 1≤ai≤109

Ví dụ

Input Output Giải thích
7
3 3 4 7 5 6 8
4
1 3 5 6
Các phần tử tại chỉ số 1,3,5,6 có giá trị 3,4,5,6. Đáp án 2 3 5 6 cũng được chấp nhận vì a2=3.
6
1 3 5 2 4 6
2
1 4
Giá trị 1,2 tại chỉ số 1,4. Không thể lấy được 3 phần tử liên tiếp vì 3 đứng trước 2.
9
6 7 8 3 4 5 9 10 11
6
1 2 3 7 8 9
Giá trị 6,7,8,9,10,11. Đoạn 3 4 5 ở giữa không nối dài được vì 6,7,8 đã đứng trước nó.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0