Java Longest Increasing Subsequence Solution
This question is quite similar to 300. longest increasing subsequence, the only difference is that we are looping through the array by k interval, and that we a
This question is quite similar to [300. longest increasing subsequence](https://leetcode.com/problems/longest-increasing-subsequence/), the only difference is that we are looping through the array by `k` interval, and that we are not restricting the condition to `strict increase` . To give a more relax definition of `increasing subsequence`, we only need to modify a few lines of code (see comments).\n\n```\nclass Solution {\n    public int kIncreasing(int[] arr, int k) {\n        int result = 0;\n        \n        for (int i = 0; i < k; i++) {\n            // check arr[i, i+k, i+2k, ...]\n            //\n            // find longest increasing sub seq\n            List<Integer> list = new ArrayList<>();\n            \n            for (int j = i; j < arr.length; j += k) {\n                list.add(arr[j]);\n            }\n            \n            int longestIncreasingSubSeq = lengthOfLIS(list);\n            \n            result += list.size() - longestIncreasingSubSeq;\n        }\n        \n        return result;\n    }\n    \n    public int lengthOfLIS(List<Integer> nums) {\n        ArrayList<Integer> sub = new ArrayList<>();\n        sub.add(nums.get(0));\n        \n        for (int i = 1; i < nums.size(); i++) {\n            int num = nums.get(i);\n            if (num >= sub.get(sub.size() - 1)) { // this >= check the `increasing subsequence` condition in this question\n                sub.add(num);\n            } else {\n                int j = binarySearch(sub, num);\n                sub.set(j, num);\n            }\n        }\n        \n        return sub.size();\n    }\n    \n    private int binarySearch(List<Integer> sub, int num) {\n        int left = 0, right = sub.size() - 1;\n        \n        while (left < right) {\n            int mid = left + (right - left) / 2;\n            \n            if (sub.get(mid) <= num) { // this <= check the `increasing subsequence` condition in this question\n                left = mid + 1;\n            } else {\n                right = mid;\n            }\n        }\n        \n        return left;\n    }\n}\n```
[]