Yêu cầu: Lập trình nhập vào một dãy số nguyên sau đó xóa bớt một số phần tử của dãy và giữ nguyên trình tự các phần tử còn lại để được dãy con lồi dài nhất.
Dữ liệu vào:
- Dòng đầu là số tự nhiên N (3 ≤ N ≤ 5000).
- Dòng tiếp theo là N số nguyên của dãy số (các số kiểu Integer), mỗi số cách nhau một kí tự trống.
Dữ liệu ra:
- Dòng đầu tiên ghi số phần tử của dãy con lồi dài nhất tìm được (Ghi số 0 nếu không tìm được).
- Trong trường hợp tìm được, dòng tiếp theo ghi dãy con lồi dài nhất vừa tìm được ở trên, mỗi số cách nhau một kí tự trống.
Chương trình ví dụ:
Mã: Chọn tất cả
Input:
10
1 2 3 4 2 5 1 2 3 4
Output:
6
4 2 1 2 3 4
Mã: Chọn tất cả
Program DayLoi;
Var N, max_i : Integer;
max : LongInt;
A, DT, LT, DG, LG : Array[0..5000] Of LongInt;
Procedure Nhap;
Var i : Integer;
Begin
Readln(N);
For i := 1 To N Do Read(A[i]);
ReadLn;
End;
Procedure TimDayGiamXuoi;
Var i, j : Integer;
Begin
DT[1] := 1;
LT[1] := 0;
For i := 2 To N Do Begin
DT[i] := 1;
LT[i] := 0;
For j := i-1 DownTo 1 Do
If (A[i] < A[j]) And (DT[i] < DT[j] + 1) Then Begin
DT[i] := DT[j] + 1;
LT[i] := j;
End;
End;
End;
Procedure TimDayGiamNguoc;
Var i, j : Integer;
Begin
DG[N] := 1;
LG[N] := 0;
For i := N-1 DownTo 1 Do Begin
DG[i] := 1;
LG[i] := 0;
For j := i + 1 To N Do
If (A[i] < A[j]) And (DG[i] < DG[j] + 1) Then Begin
DG[i] := DG[j] + 1;
LG[i] := j;
End;
End;
End;
Procedure XuLi;
var i : Integer;
Begin
max := DT[i] + DG[i];
For i := 2 To N Do
If max < DT[i] + DG[i] Then Begin
max := DT[i] + DG[i];
max_i := i;
End;
i := max_i;
While LT[i] <> 0 Do Begin
DT[i] := DT[i] * (-1);
i := LT[i];
End;
DT[i] := DT[i] * (-1);
i := LG[max_i];
While LG[i] <> 0 Do Begin
DT[i] := DT[i] * (-1);
i := LG[i];
End;
DT[i] := DT[i] * (-1);
End;
Procedure Xuat;
Var i : Integer;
Begin
WriteLn(max-1);
For i := 1 To N Do
If DT[i] < 0 Then Write(A[i], ' ');
End;
Begin
Nhap;
TimDayGiamXuoi;
TimDayGiamNguoc;
XuLi;
Xuat;
End.
Mã: Chọn tất cả
Program DayLom;
Var N, max_i : Integer;
max : LongInt;
A, DT, LT, DG, LG : Array[0..5000] Of LongInt;
Procedure Nhap;
Var i : Integer;
Begin
Readln(N);
For i := 1 To N Do Read(A[i]);
ReadLn;
End;
Procedure TimDayTangXuoi;
Var i, j : Integer;
Begin
DT[1] := 1;
LT[1] := 0;
For i := 2 To N Do Begin
DT[i] := 1;
LT[i] := 0;
For j := i-1 DownTo 1 Do
If (A[i] > A[j]) And (DT[i] < DT[j] + 1) Then Begin
DT[i] := DT[j] + 1;
LT[i] := j;
End;
End;
End;
Procedure TimDayTangNguoc;
Var i, j : Integer;
Begin
DG[N] := 1;
LG[N] := 0;
For i := N-1 DownTo 1 Do Begin
DG[i] := 1;
LG[i] := 0;
For j := i + 1 To N Do
If (A[i] > A[j]) And (DG[i] < DG[j] + 1) Then Begin
DG[i] := DG[j] + 1;
LG[i] := j;
End;
End;
End;
Procedure XuLi;
var i : Integer;
Begin
max := DT[i] + DG[i];
For i := 2 To N Do
If max < DT[i] + DG[i] Then Begin
max := DT[i] + DG[i];
max_i := i;
End;
i := max_i;
While LT[i] <> 0 Do Begin
DT[i] := DT[i] * (-1);
i := LT[i];
End;
DT[i] := DT[i] * (-1);
i := LG[max_i];
While LG[i] <> 0 Do Begin
DT[i] := DT[i] * (-1);
i := LG[i];
End;
DT[i] := DT[i] * (-1);
End;
Procedure Xuat;
Var i : Integer;
Begin
WriteLn(max-1);
For i := 1 To N Do
If DT[i] < 0 Then Write(A[i], ' ');
End;
Begin
Nhap;
TimDayTangXuoi;
TimDayTangNguoc;
XuLi;
Xuat;
End.