Advertisement
Josif_tepe

Untitled

May 12th, 2022
590
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.Scanner;
  2.  
  3.  
  4. public class LDS {
  5.  
  6.     private static int[] niza;
  7.     static int[] dp;
  8.     static int rec(int idx) {
  9.         if(idx == niza.length - 1) {
  10.            return 1;
  11.         }
  12.         if(dp[idx] != -1) {
  13.             return dp[idx];
  14.         }
  15.         int result = 1;
  16.         for(int i = idx + 1; i < niza.length; i++) {
  17.             if(niza[idx] > niza[i]) {
  18.                 result = Math.max(result, rec(i) + 1);
  19.             }
  20.         }
  21.         dp[idx] = result;
  22.     return result;
  23.     }
  24.  
  25.     private static int najdolgaOpagackaSekvenca(int[] a) {
  26.  
  27.         niza = new int[a.length];
  28.         niza = a;
  29.         int result = 0;
  30.         dp = new int[a.length];
  31.         for(int i = 0; i < a.length; i++) {
  32.             dp[i] = -1;
  33.         }
  34.         for(int i = 0; i < a.length; i++) {
  35.             result = Math.max(result, rec(i));
  36.         }
  37.         return result;
  38.     }
  39.  
  40.     public static void main(String[] args) {
  41.         Scanner stdin = new Scanner(System.in);
  42.  
  43.         int n = stdin.nextInt();
  44.         int a[] = new int[n];
  45.         for (int i = 0; i < a.length; i++) {
  46.             a[i] = stdin.nextInt();
  47.         }
  48.         System.out.println(najdolgaOpagackaSekvenca(a));
  49.     }
  50.  
  51.  
  52. }
  53.  
Advertisement
RAW Paste Data Copied
Advertisement