Question

How to find the longest increasing not sorted subsequence (LIS) of a sequence of numbers in Pascal

Answer 1

program LongestIncreasingSubsequence;

const
  MaxSize = 100;

type
  TIntArray = array[1..MaxSize] of Integer;

function LIS(nums: TIntArray; n: Integer): Integer;
var
  length: TIntArray;
  i, j, maxLength: Integer;
begin
  for i := 1 to n do
    length[i] := 1;

  maxLength := 1;

  for i := 2 to n do
  begin
    for j := 1 to i - 1 do
    begin
      if nums[i] > nums[j] then
        if length[i] < length[j] + 1 then
          length[i] := length[j] + 1;
    end;
    if maxLength < length[i] then
      maxLength := length[i];
  end;

  LIS := maxLength;
end;

var
  nums: TIntArray;
  n, result: Integer;
begin
  nums[1] := 4;
  nums[2] := 5;
  nums[3] := 1;
  nums[4] := 10;
  nums[5] := 3;
  nums[6] := 9;
  nums[7] := 18;
  nums[8] := 19;
  n := 8;

  result := LIS(nums, n);
  WriteLn('Length of LIS: ', result);
end.



(*
run:

Length of LIS: 5

*)

 

70+ SQL courses for beginners and professionals