Tìm chuỗi con không giảm dài nhất trong Pascal

Chuỗi con không giảm dài nhất (Longest Increasing Subsequence) là một chuỗi con trong dãy số đầu vào mà các phần tử trong chuỗi con đó được sắp xếp theo thứ tự không giảm.

Trong Pascal, ta có thể sử dụng thuật toán Dynamic Programming để tìm chuỗi con không giảm dài nhất (LIS) của một dãy số. Cụ thể, ta có thể sử dụng một mảng dp với độ dài bằng với độ dài của dãy số đầu vào để lưu độ dài của LIS tại mỗi vị trí.

Với mỗi vị trí i trong dãy số đầu vào, ta duyệt qua tất cả các vị trí j trước đó (j < i), nếu số tại vị trí i lớn hơn số tại vị trí j và dp[j] + 1 lớn hơn dp[i] thì ta cập nhật dp[i] = dp[j] + 1.

Sau khi duyệt xong, LIS có độ dài lớn nhất sẽ là giá trị lớn nhất trong mảng dp.

Dưới đây là mã Pascal mô tả thuật toán trên:

function LongestIncreasingSubsequence(arr: array of Integer): Integer;
var
  n, i, j: Integer;
  dp: array of Integer;
begin
  n := Length(arr);
  SetLength(dp, n);
  
  for i := 0 to n - 1 do
  begin
    dp[i] := 1;
    for j := 0 to i - 1 do
    begin
      if (arr[i] > arr[j]) and (dp[j] + 1 > dp[i]) then
        dp[i] := dp[j] + 1;
    end;
  end;

  Result := 0;
  for i := 0 to n - 1 do
  begin
    if dp[i] > Result then
      Result := dp[i];
  end;
end;

Bạn có thể sử dụng hàm LongestIncreasingSubsequence này để tìm chuỗi con không giảm dài nhất của một dãy số bất kỳ.

Dưới đây là một ví dụ cụ thể về việc sử dụng hàm LongestIncreasingSubsequence để tìm chuỗi con không giảm dài nhất của một dãy số trong Pascal:

program LISExample;

function LongestIncreasingSubsequence(arr: array of Integer): Integer;
var
  n, i, j: Integer;
  dp: array of Integer;
begin
  n := Length(arr);
  SetLength(dp, n);
  
  for i := 0 to n - 1 do
  begin
    dp[i] := 1;
    for j := 0 to i - 1 do
    begin
      if (arr[i] > arr[j]) and (dp[j] + 1 > dp[i]) then
        dp[i] := dp[j] + 1;
    end;
  end;

  Result := 0;
  for i := 0 to n - 1 do
  begin
    if dp[i] > Result then
      Result := dp[i];
  end;
end;

var
  arr: array of Integer;
  n, i: Integer;
begin
  // Nhập dãy số từ bàn phím
  Write('Nhap so phan tu cua day: ');
  ReadLn(n);
  SetLength(arr, n);
  for i := 0 to n - 1 do
  begin
    Write('Nhap phan tu thu ', i + 1, ': ');
    ReadLn(arr[i]);
  end;

  // Tìm chuỗi con không giảm dài nhất
  WriteLn('Chuoi con khong giam dai nhat la: ', LongestIncreasingSubsequence(arr));
end.

Ví dụ: Nếu ta nhập dãy số [1, 3, 2, 4, 5, 2, 6, 7], chương trình sẽ xuất ra kết quả là “Chuoi con khong giam dai nhat la: 5”, cho biết chuỗi con không giảm dài nhất của dãy số này có độ dài là 5 và là [1, 3, 4, 6, 7].

Lập trình Pascal

Tìm chuỗi con không giảm dài nhất trong Pascal

Trả lời Hủy