package LeetCode;

import java.util.ArrayList;
import java.util.List;

public class LC_376_wrong {
    static List<List<Integer>> res = new ArrayList<>();
    static ArrayList<Integer> path = new ArrayList<>();
    static int maxLen = 0;

    public static void main(String[] args) {
        int[] nums = {33,53,12,64,50,41,45,21,97,35,47,92,39,0,93,55,40,46,69,42,6,95,51,68,72,9,32,84,34,64,6,2,26,98,3,43,30,60,3,68,82,9,97,19,27,98,99,4,30,96,37,9,78,43,64,4,65,30,84,90,87,64,18,50,60,1,40,32,48,50,76,100,57,29,63,53,46,57,93,98,42,80,82,9,41,55,69,84,82,79,30,79,18,97,67,23,52,38,74,15};
        wiggleMaxLength(nums);
    }

    public static int wiggleMaxLength(int[] nums) {
        backtracking(nums, 0);
        System.out.println(maxLen);
        System.out.println(res);
        return maxLen;
    }

    public static void backtracking(int[] nums, int startIdx) {
        if (startIdx > nums.length) return;
        if (isValid(path)) {
            if (maxLen < path.size()) maxLen = path.size();
            res.add(new ArrayList<>(path));
        }
        for (int i = startIdx; i < nums.length; i++) {
            path.add(nums[i]);
            backtracking(nums, i + 1);
            path.remove(path.size() - 1);
        }
    }

    public static boolean isValid(ArrayList<Integer> path) {
        if (path.size() == 1) return true;
        if (path.size() == 2)
            if (path.get(0) != path.get(1)) return true;
        ArrayList<Integer> dif = new ArrayList<>();
        for (int i = 0; i < path.size() - 1; i++)
            if (path.get(i + 1) - path.get(i) == 0) return false;
            else dif.add(path.get(i + 1) - path.get(i) > 0 ? 1 : 0);
        for (int i = 0; i < dif.size() - 1; i++)
            if (dif.get(i) == dif.get(i + 1)) return false;
        return true;
    }
}