C++ Simple LIS Simple and Short Solution Explained
\n//function to calculate LIS in O(n*logn) using binary search and DP\n//NOTE : O(n*n) method of finding LIS will give TLE\nint helper(vector<int>&nums){\n     
```\n//function to calculate LIS in O(n*logn) using binary search and DP\n//NOTE : O(n*n) method of finding LIS will give TLE\nint helper(vector<int>&nums){\n          vector<int> lis;\n        for (int i = 0; i < nums.size(); ++i) {\n            int x = nums[i];\n            if (lis.empty() || lis[lis.size() - 1] <= x) { \n                lis.push_back(x);\n                nums[i] = lis.size();\n            } else {\n                int idx = upper_bound(lis.begin(), lis.end(), x) - lis.begin(); \n                lis[idx] = x; \n                nums[i] = idx + 1;\n            }\n        }\n        // cout<<lis.size()<<endl;\n        return lis.size();\n    }\n\nint kIncreasing(vector<int>& arr, int k) {\n        \n        int res = 0;\n        \n\t\t//in this ques , we only have to form k sub seq\n\t\t//for each subarray the answer will be\n\t\t//len(curr_subseq) - len(lis in that sub seq)\n\t\t//hence, adding ans for all k sub seq\n\t\t// we get our required answer\n        for(int i=0;i<k;i++)\n        {\n            vector<int> temp;\n            for(int j=i;j<size(arr);j+=k)\n                temp.push_back(arr[j]);\n            \n            res += size(temp) - helper(temp);\n        }\n        \n        return res;\n    }\n```
['Dynamic Programming', 'Binary Tree']