Guest User

LongestZigZagSubsequence

a guest
May 22nd, 2019
38
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.io.BufferedReader;
  2. import java.io.InputStreamReader;
  3. import java.util.Arrays;
  4.  
  5. import static java.lang.Integer.parseInt;
  6.  
  7. /**
  8.  * Created by bugkiller on 21/10/18.
  9.  */
  10. class LongestZigZagSubsequence {
  11.  
  12.  
  13.     public static void main(String[] args) throws Exception {
  14.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  15.         int t = parseInt(br.readLine());
  16.         while (t-- > 0) {
  17.             int n = parseInt(br.readLine());
  18.             String s[] = br.readLine().split("\\s");
  19.             int a[] = new int[n];
  20.             for (int i = 0; i < n; i++) {
  21.                 a[i] = parseInt(s[i]);
  22.             }
  23.             System.out.println(longestZigZagSubsequence(a));
  24.         }
  25.     }
  26.     //This is the incorrect solution and needs to be fixed.
  27.     public static int longestZigZagSubsequence(int a[]) {
  28.         int ans = 0;
  29.         for (int i = 0; i < a.length; i++) {
  30.             ans = max(ans,
  31.                       longestZigZagSubsequence(a, i, Integer.MIN_VALUE, true),
  32.                       longestZigZagSubsequence(a, i, Integer.MAX_VALUE, false));
  33.         }
  34.         return ans;
  35.     }
  36.     private static int longestZigZagSubsequence(int[] a, int idx, int prev, boolean biggerElementNeeded) {
  37.         if (a.length == idx) return 0;
  38.         if (a[idx] > prev && biggerElementNeeded) {
  39.             return 1 + longestZigZagSubsequence(a, idx + 1, a[idx], false);
  40.         }
  41.         if (!biggerElementNeeded && prev > a[idx]) {
  42.             return 1 + longestZigZagSubsequence(a, idx + 1, a[idx], true);
  43.         }
  44.         return longestZigZagSubsequence(a, idx + 1, prev, biggerElementNeeded);
  45.     }
  46.  
  47.     private static int max(int a, int b, int c) {
  48.         return Integer.max(a, Integer.max(b, c));
  49.     }
  50.  
  51. }
RAW Paste Data