1003

Đề bài: Cho dãy con gồm N phần tử, hãy tìm ra dãy con tăng dần gồm nhiều phần tử nhất.
Dữ liệu vào được lấy từ tệp input.txt, tệp này gồm 2 dòng
+ dòng 1 : chứa số N
+ dòng 2: chứa N số nguyên, các số cách nhau ít nhất 1 dấu cách và có giá trị trong phạm vi từ [0, 100000]
kết quả tìm được đưa ra tệp output.txt gồm 2 số là vị trí bắt đầu dãy con và độ dài của nó, các số cách nhau bởi 1 dấu cách
trong trường hợp có nhiều dãy con tăng cùng có độ dài lớn nhất thì đưa ra vị trí nhỏ nhất

|-------------------------------------------------------|
|       input.txt       |           output.txt          |
|-------------------------------------------------------|
|10                     |1 3                            |
|6 8 9 2 4 6 4 2 3 1    |                               |
|-------------------------------------------------------|
function kt(b: mang;m,l:word): boolean;
var ok: boolean;  {biến này sẽ cho biết dãy có là dãy tăng hay không, ok = true (dãy tăng), ok = false (dãy không tăng)}
    i:word;   {hãy thử bỏ dòng này và chạy kết quả xem sao nhá}
begin
    ok :=true;  {giả sử ban đầu nó là dãy tăng}
    i:=m;
    while ok and (i<m+l-1) do  { ở đây ta so sánh phần tử thứ i và phần tứ thứ i +1 nên i chỉ chạy đến m+l-1}
        if b[i] > b[i+1] then  ok := false {chỉ cần 1 phần tử lớn hơn phần tử đứng sau thì ta kết luận được ngay dãy không là dãy tăng (ok:=false)}
                else inc(i);
    kt := ok; {cuối cùng dãy tăng hay không phụ thuộc vào biến ok }
end;

{từ bài này, hãy vận dụng làm các bài sau:
Bài 1: Hãy sửa bài trên để đưa ra vị lớn nhất
|-------------------------------------------------------|
|       input.txt       |           output.txt          |
|-------------------------------------------------------|
|10                     |4 3                            |
|6 8 9 2 4 6 4 2 3 1    |                               |
|-------------------------------------------------------|
Bài 2: Đưa ra dãy con dài nhất mà các phần tử cùng dấuif a[i]
Bài 3: Đưa ra dãy con dài nhất mà các phần tử đan dấu (trái dấu)
Bài 4: Tìm dãy con có tăng (hoặc giảm) có tổng lớn nhất
}