Advertisement
Josif_tepe

Untitled

May 12th, 2022
555
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.57 KB | None
  1. import java.awt.event.MouseAdapter;
  2. import java.io.BufferedReader;
  3. import java.io.InputStreamReader;
  4.  
  5. public class ZigZagSequence {
  6.  
  7.     static int[] niza, 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] < 0) {
  18.                 if(niza[i] > 0) {
  19.                     result = Math.max(result, rec(i) + 1);
  20.                 }
  21.             }
  22.             else if(niza[idx] > 0) {
  23.                 if(niza[i] < 0) {
  24.                     result = Math.max(result, rec(i) + 1);
  25.                 }
  26.             }
  27.         }
  28.         dp[idx] = result;
  29.         return result;
  30.     }
  31.  
  32.     static int najdiNajdolgaCikCak(int a[]) {
  33.         niza = a;
  34.         dp = new int[a.length];
  35.         for(int i = 0; i < a.length; i++) {
  36.             dp[i] = -1;
  37.         }
  38.         int result = 0;
  39.         for(int i = 0; i < a.length; i++) {
  40.             result = Math.max(result, rec(i));
  41.         }
  42.         return result;
  43.     }
  44.  
  45.     public static void main(String[] args) throws Exception {
  46.         int i,j,k;
  47.  
  48.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  49.  
  50.         int N = Integer.parseInt(br.readLine());
  51.         int a[] = new int[N];
  52.         for (i=0;i<N;i++)
  53.             a[i] = Integer.parseInt(br.readLine());
  54.  
  55.         int rez = najdiNajdolgaCikCak(a);
  56.         System.out.println(rez);
  57.  
  58.         br.close();
  59.  
  60.     }
  61.  
  62. }
  63.  
Advertisement
RAW Paste Data Copied
Advertisement