Java | Longest non-decreasing subsequence k times
Based on 300. Longest Increasing Subsequence, but allowing duplicates in sequence (hence non-decreasing).\nTo solve the problem:\n- iterate k subsequences of th
Based on [300. Longest Increasing Subsequence](https://leetcode.com/problems/longest-increasing-subsequence/), but allowing duplicates in sequence (hence non-decreasing).\nTo solve the problem:\n- iterate k subsequences of the original sequence (elements separated by k steps belong to the same subsequence),\n- calculate LIS for each subsequence (Java note: cannot use the built-in Arrays.binarySearch() as its behavior is undefined in presence of duplicates - a weird decision in the implementation of the Java standard libraries - we have no equivalent to C++ lower_bound and upper_bound; to handle dupes we need our own upperBound() method),\n- elements NOT in LIS need to be changed to make the whole subsequence non-decreasing.\n\nComplexity: **time O(n log(n/k)), space O(n/k)**\n\nBonus materials: \n- a nice [intro to LIS](https://www.cs.princeton.edu/courses/archive/spring13/cos423/lectures/LongestIncreasingSubsequence.pdf), \n- another (partial) LIS algo problem: [334. Increasing Triplet Subsequence](https://leetcode.com/problems/increasing-triplet-subsequence/)\n\n```\nclass Solution {\n    public int kIncreasing(int[] arr, int k) {\n        int kLenLIS= 0, dp[]= new int[arr.length/k+1];\n        for(int i=0; i<k; i++)\n            kLenLIS+= lengthOfLIS(arr, i, k, dp);\n        return arr.length - kLenLIS;\n    }\n    \n    public int lengthOfLIS(int[] arr, int start, int k, int[] dp) {\n        int len= 0;\n        for(int i=start; i<arr.length; i+=k) {\n            int j= upperBound(dp, len, arr[i]);\n            if(j==len) len++;\n\t\t\tdp[j]= arr[i];\n        }\n        return len;\n    }\n    \n    int upperBound(int[] dp, int len, int num){\n        int ans= len, l= 0, r= len-1;\n        while(l<=r){\n            int mid= l+(r-l)/2;\n            if(dp[mid]<=num){\n                l= mid+1;\n            }else{\n                ans= mid;\n                r= mid-1;\n            }\n        }\n        return ans;        \n    }\n}\n```\n\n\nA concise, but much less readable version below.\n\n```\npublic int kIncreasing(int[] arr, int k) {\n\tint kLenLIS= 0, n= arr.length, dp[]= new int[n/k+1];\n\tfor(int i=0, len=0; i<k; i++, kLenLIS+=len, len=0)\n\t\tfor(int l, r, mid, ans, j=i; j<n; dp[ans==len?len++:ans]= arr[j], j+=k)\n\t\t\tfor(ans=len, l=0, r=len-1; l<=r;)\n\t\t\t\tif(dp[mid= l+(r-l)/2]<=arr[j]) l= mid+1;\n\t\t\t\telse r= (ans= mid)-1;\n\treturn n - kLenLIS;\n}\n```
[]