kotlin coding test course, finding the longest increasing subsequence

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.

Problem Description

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.

Example

    Input: [10, 22, 9, 33, 21, 50, 41, 60, 80]
    Output: 6
    Explanation: An example of the longest increasing subsequence is [10, 22, 33, 50, 60, 80].
    

Approach to Solution

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.

Step 1: Initialize the DP Table

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.

Step 2: Update the DP Table

Now, we compare all elements of the input array with each other. For each element arr[i], we check all previous elements arr[j] (j < i) and evaluate the following condition:

    if arr[i] > arr[j] then
        dp[i] = max(dp[i], dp[j] + 1)
    

Here, dp[i] is the length of the LIS that includes arr[i], and dp[j] + 1 represents the length if arr[j] is followed by arr[i].

Step 3: Derive the Result

After processing all elements, we find the largest value in the dp array and return the length of the LIS as the result.

Kotlin Implementation

Now, let’s implement it in Kotlin. Below is the code that follows the algorithm explained above.

fun longestIncreasingSubsequence(arr: IntArray): Int {
    val n = arr.size
    val dp = IntArray(n) { 1 } // initialize dp array

    for (i in 1 until n) {
        for (j in 0 until i) {
            if (arr[i] > arr[j]) {
                dp[i] = maxOf(dp[i], dp[j] + 1)
            }
        }
    }
    return dp.maxOrNull() ?: 1 // return the maximum value in dp array
}

fun main() {
    val arr = intArrayOf(10, 22, 9, 33, 21, 50, 41, 60, 80)
    val length = longestIncreasingSubsequence(arr)
    println("Length of the longest increasing subsequence: $length")
}
    

Complexity Analysis

As a result, the time complexity of this algorithm is O(n²). This is because a nested loop runs for n. The space complexity is O(n) as we need space to store the DP array.

Optimization Method

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:

import java.util.*

fun longestIncreasingSubsequenceOptimized(arr: IntArray): Int {
    if (arr.isEmpty()) return 0

    val tails = mutableListOf()

    for (num in arr) {
        val index = tails.binarySearch(num)
        if (index < 0) {
            val pos = -(index + 1)
            if (pos == tails.size) {
                tails.add(num)
            } else {
                tails[pos] = num
            }
        }
    }
    return tails.size
}
    

Here, the tails array stores the possible last elements of the LIS. Using binary search, it finds the appropriate position to insert or replace elements.

Conclusion

In this article, we explored the longest increasing subsequence problem using Kotlin. I detailed the approach to the problem and the implementation method, along with optimization techniques. Such problems are frequently asked in coding tests, so repeated practice is important. I will continue to share various algorithm problems. If you have any questions, please ask in the comments!