Đoạn không giảm dài nhất

Cho dãy gồm N số nguyên. Tìm đoạn không giảm có chiều dài lớn nhất.

MDOAN.INP	MDOAN.OUT
12 1 5 5 1 3 3 3 5 7 9 1 2	4 7

Dữ liệu vào: tệp văn bản MDOAN.INP

Dòng thứ nhất: số tự nhiên N,          1 £ N £ 20000.

Từ dòng thứ hai trở đi: các phần tử của dãy.

Dữ liệu ra: tệp văn bản MDOAN.OUT

Chứa một dòng duy nhất gồm hai số tự nhiên  d – chỉ số đầu đoạn và L – số phần tử trong đoạn (chiều dài đoạn).

Trong các tệp, dữ liệu trên cùng dòng cách nhau qua dấu cách.

Thí dụ trên cho ta đoạn không giảm dài nhất bao gồm 7 phần tử  bắt đầu từ phần tử thứ tư trong dãy (các phần tử được gạch dưới):

1 5 5 1 3 3 3 5 7 9 1 2

Thuật toán

Đây là bài dễ, ta đọc dần các phần tử từ input file và  so sánh hai phần tử liên tiếp nhau là x (phần tử đọc trước tại bước i) và y (phần tử đọc sau tại bước i+1). Nếu y < x thì coi như kết thúc một đọan không giảm, ta cập nhật để ghi nhận lại đoạn không giảm dài nhất. Các biến tổng thể trong chương trình được dùng như sau:

MaxLen – chiều dài của đoạn không giảm dài nhất hiện tìm được,

imax -  chỉ số đầu tiên của đoạn không giảm dài nhất hiện tìm được,

ileft – chỉ số đầu tiên của đoạn không giảm đang xét.

Độ phức tạp: cỡ N.

(*  Pascal  *)

(****************************************

      MDOAN - Doan tang dai nhat

****************************************)

program MDoan;

uses crt;

const

 bl = #32; fn = 'MDOAN.INP'; gn = 'MDOAN.OUT';

var f,g: text;

  n: integer;

  a: mw1;

  iLeft, imax: integer;

  MaxLen: integer;

procedure Update(i: integer);

begin

  if (MaxLen < i - iLeft) then

   begin

     MaxLen := i - iLeft;

     imax := iLeft; ileft := i;

   end;

  iLeft := i;

end;

procedure XuLi;

 var i, x, y: integer;

 begin

  assign(f,fn);  reset(f);  readln(f,n);

  read(f,x); 

   iLeft := 1;  MaxLen := 0;

   for i := 2 to n do

    begin

     read(f,y);

     if (y < x) then Update(i);

     x := y;

    end;

   Update(n+1);

  close(f);

 end;

procedure Ghi;

begin

  assign(g,gn); rewrite(g);

  writeln(g,imax,bl,MaxLen);

  close(g);

end;

BEGIN

  XuLi; ghi;

END.

Nguồn:

SÁNG TẠO

TRONG THUẬT TOÁN

VÀ

LẬP TRÌNH