To solve algorithm problems, it is crucial to understand the essence of the problem and to choose the appropriate data structures and algorithms. In this course, we will discuss the ‘Longest Increasing Subsequence (LIS)’ problem. This problem involves finding the longest possible subsequence that maintains an increasing order while processing specific data.
1. Problem Definition
The problem is to find the longest increasing subsequence in a given integer array. A subsequence means selecting some numbers from the array while maintaining their order. It is important to note that the selected numbers do not need to be contiguous. For example, given the array [10, 20, 10, 30, 20, 50], the longest increasing subsequence is [10, 20, 30, 50].
1.1 Problem Examples
Input: [10, 20, 10, 30, 20, 50]
Output: 4 (Subsequence: [10, 20, 30, 50])
Input: [5, 6, 3, 7, 8, 4, 1]
Output: 5 (Subsequence: [5, 6, 7, 8])
2. Problem Approach
The longest increasing subsequence problem can be approached with the following two basic methods:
- Dynamic Programming
- Binary Search
2.1 Dynamic Programming
Dynamic programming is a method of solving problems by breaking them down into smaller subproblems. To solve the LIS problem using dynamic programming, two arrays can be used. One array stores the length of the longest increasing subsequence for each element of the original array, and the other array stores the elements that make up that subsequence.
2.2 Binary Search
This method allows for a more efficient solution to the LIS problem. The method using binary search has a time complexity of O(n log n), and determines the position of each element by utilizing the length of the already discovered increasing subsequences during the array search process.
3. Algorithm Implementation
Below is the process of solving the LIS problem using dynamic programming and binary search implemented in Swift.
3.1 Dynamic Programming Implementation
func lengthOfLIS(_ nums: [Int]) -> Int {
guard !nums.isEmpty else { return 0 }
var dp = Array(repeating: 1, count: nums.count)
var maxLength = 1
for i in 1.. nums[j] {
dp[i] = max(dp[i], dp[j] + 1)
}
}
maxLength = max(maxLength, dp[i])
}
return maxLength
}
// Example usage
let nums = [10, 20, 10, 30, 20, 50]
print(lengthOfLIS(nums)) // Output: 4
3.2 Binary Search Implementation
func lengthOfLIS(_ nums: [Int]) -> Int {
var dp = [Int]()
for num in nums {
if let idx = dp.firstIndex(where: { $0 >= num }) {
dp[idx] = num
} else {
dp.append(num)
}
}
return dp.count
}
// Example usage
let nums = [10, 20, 10, 30, 20, 50]
print(lengthOfLIS(nums)) // Output: 4
4. Time Complexity Analysis
For dynamic programming, the time complexity is O(n^2) because a double loop is used to compare every pair of array elements. In contrast, the approach implemented with binary search has a time complexity of O(n log n), making it more efficient for handling larger inputs.
5. Conclusion
Today we discussed the problem of finding the longest increasing subsequence. We explored two approach methods: dynamic programming and binary search, analyzing each implementation and its time complexity. The process of solving such problems can be excellent practice for algorithm interviews. It is recommended to tackle various problems to prepare for coding tests.
In the next lecture, we will cover another algorithm problem. We appreciate your interest!