Longest increasing subsequence | Explanation + Code
There will be K independent arrays each having max length n/k\n  Independently find lis of all K independent arrays (using binary search/BIT)\n Minimum change =
*  There will be K **independent** arrays each having max length n/k\n*  Independently find **lis** of all K independent arrays (using binary search/BIT)\n*  **Minimum change = length of the array - lis of the array**\n*  Sum all the minimum change needed for all K arrays\n\n**CODE** (CPP)\n```\nclass Solution {\npublic:\n      int getlis(vector<int>&a) {\n            vector<int>v;\n            for (auto p : a) {\n                  auto it = upper_bound(v.begin(), v.end(), p);\n                  if (it == v.end()) {\n                        v.push_back(p);\n                  }\n                  else {\n                        *it = p;\n                  }\n            }\n            return v.size();\n      }\n      int kIncreasing(vector<int>& arr, int k) {\n            const int n = arr.size();\n            vector<vector<int>>v(k);\n            for (int i = 0; i < n; i++) {\n                  v[i % k].push_back(arr[i]);\n            }\n\n            int ans = 0;\n            for (int i = 0; i < k; i++) {\n                  int lis = getlis(v[i]);\n                  ans += v[i].size() - lis;\n            }\n            return ans;\n      }\n};\n```\n**Time complexity :**\nO((k)*(n/k)log(n/k)) = O(nlog(n/k))\n\n**Useful Problem Link**\nhttps://leetcode.com/problems/longest-increasing-subsequence/\n\n**Do Upvote** if you liked the solution.\n
['C']