How to Find the Length of the Longest Increasing Subsequence using Dynamic Programming Algorithm?

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:
Input: [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Note:
There may be more than one LIS combination, it is only necessary for you to return the length.
Your algorithm should run in O(n^2) complexity.
Follow up: Could you improve it to O(nlogn) time complexity?

Length of the Longest Increasing Subsequence using DP Algorithm

Surely, we can bruteforce, but that will take O(2^n) complexity i.e. each number has two choices: take or not take. This is not ideal. We could use f[i] to represent the longest length subsequence that ending at element nums[i]. Thus, we can reduce the runtime complexity to O(N^2) by checking each pair of (nums[j], nums[i]) and update f[i] = max(f[i], f[j] + 1) if nums[j] is smaller than nums[i].

The Longest Increasing Subsequence (LIS) can be computed via the following Dynamic Programming Algorithm i.e. C++.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if (nums.empty()) return 0;
        vector<int> f(nums.size(), 1);
        int ans = 1;
        for (int i = 1; i < nums.size(); ++ i) {
            for (int j = 0; j < i; ++ j) {
                if (nums[j] < nums[i]) {
                    f[i] = max(f[i], f[j] + 1);
                    ans = max(ans, f[i]);
                }
            }
        }
        return ans;
    }
};

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if (nums.empty()) return 0;
        vector<int> f(nums.size(), 1);
        int ans = 1;
        for (int i = 1; i < nums.size(); ++ i) {
            for (int j = 0; j < i; ++ j) {
                if (nums[j] < nums[i]) {
                    f[i] = max(f[i], f[j] + 1);
                    ans = max(ans, f[i]);
                }
            }
        }
        return ans;
    }
};

Then, we need to find out the maximum value in f[0] to f.back(). The space requirement is O(N).

Longest Increasing SubSequence

• Teaching Kids Programming – Longest Increasing Subsequence via Dynamic Programming Algorithm
• How to Find the Length of the Longest Increasing Subsequence using Dynamic Programming Algorithm?
• Teaching Kids Programming – Greedy Algorithm to Find Longest Increasing Subsequence in O(NLogN) via Binary Search

–EOF (The Ultimate Computing & Technology Blog) —