Hello! In this post, we will address the problem of “Longest Increasing Subsequence” that is frequently asked in coding tests. This problem is very helpful for understanding the basics of algorithms and building your skills. I will explain the theories for effectively solving the problem and the specific implementation process using Kotlin.<\/p>\n
The task is to find the Longest Increasing Subsequence (LIS) in a given array. A subsequence is an array formed by selecting elements from the original array in order, while maintaining the order of the original array. An increasing sequence means the elements are sorted in ascending order.<\/p>\n
\n Input: [10, 22, 9, 33, 21, 50, 41, 60, 80]\n Output: 6\n Explanation: An example of the longest increasing subsequence is [10, 22, 33, 50, 60, 80].\n <\/pre>\nApproach to Solution<\/h2>\n
The basic approach to solving this problem is to use dynamic programming (DP). DP is a method for breaking down a problem into smaller subproblems and storing previous computation results to avoid repeating the same calculations.<\/p>\n
Step 1: Initialize the DP Table<\/h3>\n
First, we initialize the DP table. We create an array to store the LIS length starting at each index of the input array. Initially, since each element itself forms a subsequence, all values are set to 1.<\/p>\n
Step 2: Update the DP Table<\/h3>\n
Now, we compare all elements of the input array with each other. For each element
arr[i]<\/code>, we check all previous elementsarr[j]<\/code> (j < i) and evaluate the following condition:<\/p>\n\n if arr[i] > arr[j] then\n dp[i] = max(dp[i], dp[j] + 1)\n <\/pre>\nHere,
dp[i]<\/code> is the length of the LIS that includesarr[i]<\/code>, anddp[j] + 1<\/code> represents the length ifarr[j]<\/code> is followed byarr[i]<\/code>.<\/p>\nStep 3: Derive the Result<\/h3>\n
After processing all elements, we find the largest value in the
dp<\/code> array and return the length of the LIS as the result.<\/p>\nKotlin Implementation<\/h2>\n
Now, let\u2019s implement it in Kotlin. Below is the code that follows the algorithm explained above.<\/p>\n
\nfun longestIncreasingSubsequence(arr: IntArray): Int {\n val n = arr.size\n val dp = IntArray(n) { 1 } \/\/ initialize dp array\n\n for (i in 1 until n) {\n for (j in 0 until i) {\n if (arr[i] > arr[j]) {\n dp[i] = maxOf(dp[i], dp[j] + 1)\n }\n }\n }\n return dp.maxOrNull() ?: 1 \/\/ return the maximum value in dp array\n}\n\nfun main() {\n val arr = intArrayOf(10, 22, 9, 33, 21, 50, 41, 60, 80)\n val length = longestIncreasingSubsequence(arr)\n println(\"Length of the longest increasing subsequence: $length\")\n}\n <\/code><\/pre>\nComplexity Analysis<\/h2>\n
As a result, the time complexity of this algorithm is O(n\u00b2). This is because a nested loop runs for n. The space complexity is O(n) as we need space to store the DP array.<\/p>\n
Optimization Method<\/h2>\n
If higher performance is required, the LIS problem can be solved using binary search, achieving O(n log n). This method is implemented as follows:<\/p>\n
\nimport java.util.*\n\nfun longestIncreasingSubsequenceOptimized(arr: IntArray): Int {\n if (arr.isEmpty()) return 0\n\n val tails = mutableListOf()\n\n for (num in arr) {\n val index = tails.binarySearch(num)\n if (index < 0) {\n val pos = -(index + 1)\n if (pos == tails.size) {\n tails.add(num)\n } else {\n tails[pos] = num\n }\n }\n }\n return tails.size\n}\n <\/code><\/pre>\n