Advertisement
CR7CR7

lseq

Oct 12th, 2022
782
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.03 KB | None | 0 0
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. import java.nio.charset.StandardCharsets;
  5. import java.util.Arrays;
  6.  
  7. public class Pr02LongestIncreasingSubsequents {
  8.  
  9.  
  10.     public static void main(final String[] args) {
  11.  
  12.         try (final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in, StandardCharsets.UTF_8))) {
  13.  
  14.             int[] numbers = Arrays
  15.                     .stream(reader.readLine().trim().split("\\s+"))
  16.                     .mapToInt(Integer::parseInt)
  17.                     .toArray();
  18.  
  19.             int[] lis = new int[numbers.length];    // Longest increasing sequence for the index
  20.             int[] prev = new int[numbers.length];   // For backtracking of the solution
  21.  
  22.             for (int currentIndex = 0; currentIndex < numbers.length; currentIndex++) {
  23.  
  24.                 lis[currentIndex] = 1;
  25.                 prev[currentIndex] = -1;
  26.  
  27.                 for (int prevIndex = 0; prevIndex < currentIndex; prevIndex++) {
  28.  
  29.                     if (numbers[prevIndex] < numbers[currentIndex] &&
  30.                             lis[prevIndex] >= lis[currentIndex]) {
  31.  
  32.                         lis[currentIndex] = lis[prevIndex] + 1;
  33.                         prev[currentIndex] = prevIndex;
  34.                     }
  35.                 }
  36.             }
  37.  
  38.             int lastIndex = -1;
  39.             int maxLen = 0;
  40.  
  41.             for (int index = 0; index < numbers.length; index++) {
  42.                 if (maxLen < lis[index]) {
  43.                     maxLen = lis[index];
  44.                     lastIndex = index;
  45.                 }
  46.             }
  47.  
  48.             int[] lisElements = new int[maxLen];
  49.  
  50.             while (lastIndex != -1) {
  51.                 lisElements[--maxLen] = numbers[lastIndex];
  52.                 lastIndex = prev[lastIndex];
  53.             }
  54.  
  55.             System.out.println(Arrays.toString(lisElements).replaceAll("[,\\[\\]]", "").trim());
  56.  
  57.         } catch (IOException | NullPointerException e) {
  58.             e.printStackTrace();
  59.         }
  60.     }
  61. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement