<commit_before>package coding4fun;

/**
 *
 */
public class Problem39 {
    private static class Node {
        private final int value;
        private Node left;
        private Node right;

        private Node(int value) {
            this.value = value;
        }

        @Override
        public String toString() {
            return Integer.toString(value);
        }
    }

//    private static class Group {
//        private int group;
//    }
//
//    private static int maxBST(Node root) {
//        Map<Integer, Integer> groupCount = new HashMap<>();
//        maxBST(root, new Group(), groupCount, 0);
//        System.out.println(groupCount);
//        return 0;
//    }
//
//    private static void maxBST(Node node, Group group, Map<Integer, Integer> groupCount,
//                               int groupNumber) {
//        if (node == null) {
//            return;
//        }
//        int newGroupNumber = groupNumber;
//        int leftGroupNumber = newGroupNumber;
//        int rightGroupNumber = newGroupNumber;
//        if (node.left != null && node.right != null) {
//            if (node.left.value < node.value && node.value < node.right.value) {
//                if (!groupCount.containsKey(newGroupNumber)) {
//                    System.out.println("root both: " + node + ", group: " + newGroupNumber);
//                    groupCount.put(newGroupNumber, 2);
//                } else {
//                    groupCount.put(newGroupNumber, groupCount.get(newGroupNumber) + 2);
//                }
//            } else {
//                leftGroupNumber = group.group++;
//                rightGroupNumber = group.group++;
//            }
//        } else if (node.left != null) {
//            if (node.left.value < node.value) {
//                if (!groupCount.containsKey(newGroupNumber)) {
//                    System.out.println("root left: " + node + ", group: " + newGroupNumber);
//                    groupCount.put(newGroupNumber, 1);
//                } else {
//                    groupCount.put(newGroupNumber, groupCount.get(newGroupNumber) + 1);
//                }
//            } else {
//                leftGroupNumber = group.group++;
//            }
//        } else if (node.right != null) {
//            if (node.value < node.right.value) {
//                if (!groupCount.containsKey(newGroupNumber)) {
//                    System.out.println("root right: " + node + ", group: " + newGroupNumber);
//                    groupCount.put(newGroupNumber, 1);
//                } else {
//                    groupCount.put(newGroupNumber, groupCount.get(newGroupNumber) + 1);
//                }
//            } else {
//                rightGroupNumber = group.group++;
//            }
//        }
//        maxBST(node.left, group, groupCount, leftGroupNumber);
//        maxBST(node.right, group, groupCount, rightGroupNumber);
//    }

    private static int maxBST(Node root) {
        if (isBST(root)) {
            System.out.println("root: " + root + " --> " + size(root));
            return size(root);<commit_msg>Add problem 39<commit_after>package coding4fun;

/**
 * Find the maximum binary search subtree from a given binary tree.
 *
 * <pre>
 * Input:
 *       1
 *      / \
 *     5   3
 *    / \   \
 *   2   9   8
 *      / \
 *     7  12
 *    / \   \
 *   10  9  13
 *  /       /
 * 6       15
 *        /  \
 *       4   18
 *
 * Output: 3
 *         subtree: 15
 *                 /  \
 *                4   18
 * </pre>
 */
public class Problem39 {
    private static class Node {
        private final int value;
        private Node left;
        private Node right;

        private Node(int value) {
            this.value = value;
        }

        @Override
        public String toString() {
            return Integer.toString(value);
        }
    }

//    private static class Group {
//        private int group;
//    }
//
//    private static int maxBST(Node root) {
//        Map<Integer, Integer> groupCount = new HashMap<>();
//        maxBST(root, new Group(), groupCount, 0);
//        System.out.println(groupCount);
//        return 0;
//    }
//
//    private static void maxBST(Node node, Group group, Map<Integer, Integer> groupCount,
//                               int groupNumber) {
//        if (node == null) {
//            return;
//        }
//        int newGroupNumber = groupNumber;
//        int leftGroupNumber = newGroupNumber;
//        int rightGroupNumber = newGroupNumber;
//        if (node.left != null && node.right != null) {
//            if (node.left.value < node.value && node.value < node.right.value) {
//                if (!groupCount.containsKey(newGroupNumber)) {
//                    System.out.println("root both: " + node + ", group: " + newGroupNumber);
//                    groupCount.put(newGroupNumber, 2);
//                } else {
//                    groupCount.put(newGroupNumber, groupCount.get(newGroupNumber) + 2);
//                }
//            } else {
//                leftGroupNumber = group.group++;
//                rightGroupNumber = group.group++;
//            }
//        } else if (node.left != null) {
//            if (node.left.value < node.value) {
//                if (!groupCount.containsKey(newGroupNumber)) {
//                    System.out.println("root left: " + node + ", group: " + newGroupNumber);
//                    groupCount.put(newGroupNumber, 1);
//                } else {
//                    groupCount.put(newGroupNumber, groupCount.get(newGroupNumber) + 1);
//                }
//            } else {
//                leftGroupNumber = group.group++;
//            }
//        } else if (node.right != null) {
//            if (node.value < node.right.value) {
//                if (!groupCount.containsKey(newGroupNumber)) {
//                    System.out.println("root right: " + node + ", group: " + newGroupNumber);
//                    groupCount.put(newGroupNumber, 1);
//                } else {
//                    groupCount.put(newGroupNumber, groupCount.get(newGroupNumber) + 1);
//                }
//            } else {
//                rightGroupNumber = group.group++;
//            }
//        }
//        maxBST(node.left, group, groupCount, leftGroupNumber);
//        maxBST(node.right, group, groupCount, rightGroupNumber);
//    }

    private static int maxBST(Node root) {
        if (isBST(root)) {
            return size(root);
{'fraction_non_alphanumeric': 0.14084724799010515, 'fraction_numerical': 0.007730364873222016, 'mean_word_length': 1.3592268417213713, 'pattern_counts': {'":': 0, '<': 19, '<?xml version=': 0, '>': 12, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5512411', 'n_tokens_mistral': 1843, 'n_tokens_neox': 1764, 'n_words': 381}