scmax

MODULE upseq;

IMPORT In, Out;

CONST MAX = 10000;

VAR xList, yList, lis, prev : ARRAY MAX OF INTEGER;
VAR n, k : INTEGER;  (* n is the size of xList and yList; k is the ending index of the longest increasing subsequence *)


(* reads the input and saves the lists into xList and yList *)

PROCEDURE Input;
  VAR x, y : INTEGER;
BEGIN
  n := 0;
  LOOP
    IF ~In.Done THEN EXIT END;
    In.Int(x);
    In.Int(y);
    xList[n] := x;
    yList[n] := y;
    n := n+1
  END
END Input;


(* dynamic quadratic algorithm to find the Longest Increasing Subsequence *)

PROCEDURE LIS;
  VAR i, j: INTEGER;
BEGIN
  lis[0] := 1;
  prev[0] := -1;
  k := 0;

  (* finds the length of the longest increasing subsequence in yList[0..i] *)
  FOR i := 1 TO n-1 DO
    lis[i] := 1;
    prev[i] := -1;
    FOR j := 0 TO i-1 DO
      IF (yList[j] < yList[i]) & (lis[j] >= lis[i]) THEN
        lis[i] := 1 + lis[j];
        prev[i] := j;
        IF lis[i] > lis[k] THEN
          k := i;
        END
      END
    END
  END
END LIS;


(* recursive proc that prints the longest increasing subsequence with the use of prev and lis *)

PROCEDURE Print(x : INTEGER);
BEGIN
  IF x = -1 THEN
    RETURN
  END;
  Print(prev[x]);
  Out.Int(xList[x], 0); Out.String(" "); Out.Int(yList[x], 0); Out.Ln

END Print;

BEGIN
  Input;
  LIS;
  IF n # 0 THEN
    Print(k)
  ELSE
    Out.String("Empty or invalid input"); Out.Ln
  END
END upseq.