Giúp mình hiểu chỗ code này

[Pham_Viet_Quang (Quang Pham)]

Edit: Mình đã hiểu ra vấn đề… thực ra khá dễ hiểu chắc tại hôm nay đầu óc không được minh mẫn

---

Mình đang học mấy thuật toán trong sách Tài liệu chuyên tin 1 của Lê Minh Hoàng , và học đến phần qhđ thì có bài ví dụ tìm dãy con đơn điệu tăng dài nhất nhưng có một chỗ mình đọc mãi không hiểu nhưng gõ code chạy trên máy thì ra kq đúng

a[0]:= low(longint);
a[n+1]:= high(longint);
L[n+1]:= 1;
for i:= n downto 0 do begin
	jmax:= n+1;
	for j:= i+1 to n+1 do 
		if (a[j]>a[i]) and (L[j] > L[jmax]) then jmax:= j; 
		l[i]:= l[jmax] + 1;
		trace[i]:= jmax;
	end;
end;
writeln(l[0]-2);
end

Đây ở chỗ này

if (a[j]>a[i]) and (L[j] > L[jmax]) then jmax:=j;   

theo mình nghĩ thì lúc khai báo mảng trong pascal các giá trị trong mảng đều mang gt = 0 , vậy làm sao mà điều kiện L[j] > L[jmax] lại thỏa mãn được.
các bạn giải thích giùm mình với , thắc mắc cả ngày hôm nay rồi

[Pham_Viet_Quang (Quang Pham)]

cảm ơn ad @hungaya đã edit bài giúp mình tại mình ít khi post bài nên chưa rõ lắm chỗ ấy

[Thanh_Nguyen20 (Anh chàng Doggo)]

Nó không thoả thì cứ suy nghĩ theo kiểu nó không thoả thôi, xD
Ngay vòng lặp đầu tiên, L[j] (hay L[n+1]) bằng 1, vẫn bằng giá trị của L[jmax] (cũng tức L[n+1]), thế nên không thực hiện phần jmax:= j, vậy jmax lúc này vẫn bằng n + 1. Sau đó gán L[i] := L[jmax] + 1 = 2. (hay L[n] := L[n+1] + 1). Nghĩa là đằng sau phần tử n có một phần tử lớn hơn nó, tính cả nó thì dãy con tăng từ n đến n+1 = 2 phần tử.
Vậy thằng L[0] sẽ có giá trị bằng với 1 + 1 + L[max], (với con 1 đằng trước là phần tử cầm canh, max là index của phần tử lớn nhất của mảng L sao cho thoả a[0] < a[max], sau đó cộng thêm 1, tức là tính cả chính nó). Xuất thì ta trừ đi 2 thằng cầm canh, vậy nên ra được dòng

writeln(l[0]-2);

Hmm, mình giải thích phần cầm canh đúng chưa nhỉ, hơi băn khoăn chỗ đấy.

[Pham_Viet_Quang (Quang Pham)]

tks bạn , để mình suy nghĩ thêm xíu nữa

[rogp10]

Kí hiệu như cũ thì:

• L[1] = 1
• L[n] = 1 + L[1..n-1].max_if( (_, index) => a[index] < a[n], 0) số 0 này là có lí do.

hay L << 1 + L.max_if...

p/s: Bài này có hai lính canh là vì:

• Lính canh ở đuôi (theo code trên): max của tập rỗng bằng mấy
• Lính canh ở đầu: để max tụ hết về đầu thay vì phải đi lấy max lần nữa. Nhưng do 0 là lính canh nên suy cho cùng chỉ có một lính canh là buộc phải có.