Introduction

The Longest Increasing Subsequence (LIS) is a fundamental problem in computer science and is crucial in fields such as bioinformatics, economics, and more. The problem is defined as follows: Given an unsorted array of integers, find the length of the longest subsequence such that all elements of the subsequence are sorted in increasing order. A subsequence is derived by deleting some or no elements of the array without changing the order of the remaining elements.

Dynamic programming is an efficient approach to solve the LIS problem, reducing the time complexity significantly compared to a naive approach. In this article, we will delve into how dynamic programming can be used to determine the LIS, along with technical explanations and examples for better understanding.

The Dynamic Programming Approach

Concept

Dynamic Programming (DP) is a method for solving complex problems by breaking them down into simpler overlapping subproblems. It is particularly useful for optimization problems because it stores the results of subproblems to avoid redundant computing.

For the LIS problem, the idea is to construct an array, dp[], where dp[i] stores the length of the LIS ending at index i. The final answer will be the maximum value in the dp[] array.

Steps

1. Initialization: Start by setting dp[i] = 1 for all elements in the array. This is because every element is an increasing subsequence of length 1 by itself.
2. Iterate and Compare: Loop through each element from the start of the array, and for each element i, loop through all previous elements j < i. Compare if the element at j is less than the element at i (nums[j] < nums[i]).
3. Update the dp Array: If nums[j] < nums[i], update dp[i] = max(dp[i], dp[j] + 1) to maintain the largest possible increasing subsequence length at i.
4. Return the Maximum: Finally, the length of the longest increasing subsequence will be the maximum value in dp[] which can be found using max(dp).

Time Complexity

The time complexity of this DP approach is $O(n^2)$ where n is the number of elements in the input array. This is attributed to the two nested loops used for iteration and comparison.

Example

Imagine you have the array: [10, 9, 2, 5, 3, 7, 101, 18]. Below is the step-by-step process of determining the LIS:

• Initialization: dp = [1, 1, 1, 1, 1, 1, 1, 1]
• Processing:
  • For i=1, compare with nums[0]: No update as nums[0] is not less than nums[1].
  • For i=2, compare with nums[0] and nums[1]: No update needed.
  • For i=3, compare with nums[0], nums[1], nums[2]:
    • nums[2] < nums[3] so dp[3] = max(dp[3], dp[2] + 1) => dp[3] = 2
  • Continue this process until all indices are processed:
    • dp = [1, 1, 1, 2, 2, 3, 4, 4]
• Result: max(dp) = 4, meaning the LIS length is 4 and one such subsequence could be [2, 3, 7, 101].

Summary Table

Conclusion

The dynamic programming approach efficiently solves the Longest Increasing Subsequence problem within a reasonable time complexity of $O(n^2)$. It is a classic example demonstrating the power of dynamic programming to deal with optimization problems by avoiding redundant calculations and storing results of subproblems for use in solving larger problems. Understanding this approach is not only beneficial for solving similar problems but also provides insights into devising efficient algorithms for complex problems.