Đoạn đơn điệu dài nhất

Đoạn đơn điệu dài nhất

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

DONDIEU.INP	DONDIEU.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 DONDIEU.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 DONDIEU.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.

Thuật toán

Edsger Wybe Dijkstra (1930-2002) Sinh năm 1930 tại Rotterdam, Holland. 1948-1956 học Toán và Vật lý lý thuyết tại Đại học Leyden. 1952-1962 nghiên cứu tại Trung tâm Toán học Amsterdam. 1962-1973 Giáo sư Toán tại Đại học Bách khoa Eindhoven, Holland và Đại học Texas Austin. Dijkstra là một trong những người đi tiên phong trong lĩnh vực lập trình, người khởi xướng và đặt nền móng cho nguyên lý lập trình cấu trúc.

Edsger Wybe Dijkstra (photo ©2002 Hamilton Richards)

Nhận xét:

Đoạn có 1 phần tử là đoạn đơn điệu (tăng, giảm),

Đoạn gồm một dãy liên tiếp các phần tử bằng nhau là đoạn đơn điệu (tăng, giảm).

Ta dùng hai biến đếm các phần tử tăng hoặc bằng nhau liên tiếp, dt và đếm các phần tử giảm hoặc bằng nhau liên tiếp, dg. Nếu a_i = a_i-1 ta tăng đồng thời dt và dg 1 đơn vị. Nếu a_i > a_i-1 ta tăng dt thêm 1 đơn vị và đặt lại dg = 1. Nếu a_i < a_i-1 ta tăng dg thêm 1 đơn vị và chỉnh lại dt = 1. Sau mỗi bước ta cập nhật đoạn đơn điệu dài nhất tìm được. Chương trình Pascal đọc và xử lí trực tiếp file input, chương trình C# đọc toàn bộ dữ liệu vào mảng rồi xử lí trên mảng.

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

Các biến tổng thể:

n: số lượng phần tử,

dt: đếm số phần tử trong dãy tăng,

dg: đếm số phần tử trong dãy giảm.

iMax: chỉ số đầu của đoạn đơn điệu dài nhất,

MaxLen: chiều dài (số phần tử) của đoạn đơn điệu dài nhất.

(*  Pascal  *)

program DonDieu;

uses crt;

const

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

var f,g: text;

  n: integer;

  dt,dg: integer;

  iMax, MaxLen: integer;

function Max(a,b,c: integer): integer;

begin

  if (a < b) then a := b; { a = Max(a,b) }

  if (a > c) then Max := a

    else Max := c;

end;

procedure XuLi;

 var i,m,x,y: integer;

 begin

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

   readln(f,n); read(f,x);

   dt := 1; dg := 1;

   MaxLen := 1; iMax := 1;

   for i := 2 to n do

    begin

     read(f,y);

     if (y = x) then

       begin  dt := dt + 1;  dg := dg + 1; end

       else if (y > x) then

        begin  dt := dt + 1;  dg := 1;  end

       else { y < x }

        begin  dg := dg + 1;  dt := 1;  end;

     m := Max(MaxLen, dt, dg);

     if (m > MaxLen) then

       begin  MaxLen := m; iMax := i - MaxLen + 1;  end;

     x := y;

    end;

   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