Dãy con đơn điệu tăng dài nhất

Bài toán. Cho dãy số nguyên A = a1, a2, …, an (1≤n≤5000, -10000≤ai≤10000). Một dãy con của A là một cách chọn ra trong A một số phần tử và giữ nguyên thứ tự.

Yêu cầu: Tìm dãy con đơn điệu tăng của dãy A có độ dài lớn nhất.

Dữ liệu vào: Cho từ file văn bản INCSEQ.INP

Dòng đầu ghi số n
Dòng thứ hai ghi n số a1, a2, …, an cách nhau ít nhất một dấu cách.

Kết quả: Ghi ra file văn bản INCSEQ.OUT

Dòng đầu ghi độ dài của dãy con tìm được
Các dòng tiếp theo, mỗi dòng ghi hai số tương ứng là chỉ số và giá trị của phần tử được chọn trong dãy A theo thứ tự từ đầu đến cuối.

Ví dụ:

INCSEQ.INP

INCSEQ.OUT

3 9 4 8 6 2 1 7 10 5

1 3

3 4

5 6

8 7

9 10

Const fin ='INCSEQ.INP';
      fout='INCSEQ.OUT';
Var L,Truoc,a:array[1..5001] of integer;
    n,m,i,k:integer;
    f:text;
Begin
  Assign(f,fin);
  Reset(f);
  Readln(f,n);
  For i:=1 to n do Read(f,a[i]);
  Close(f);
 
  L[n+1]:=0;
  For k:=n downto 1 do
    Begin
      m:=n+1;
      For i:=k+1 to n do
        If (a[k]<a[i]) and (L[i]>L[m]) then m:=i;
      L[k]:=L[m]+1;
      Truoc[k]:=m;
    End;
  m:=1;
  For i:=2 to n do
    If L[i]>L[m] then m:=i;
  Assign(f,fout);
  ReWrite(f);
  Writeln(f,L[m]);
  Repeat
    Writeln(f,m,' ',a[m]);
    m:=Truoc[m];
  Until m>n;
  Close(f);
End.

Click vào đây để làm thử và chấm thử

Cùng chuyên mục