Longest increasing subsequence

The longest run of values that keeps rising, where you may skip elements but not reorder them.

Time O(n²)Space O(n)Code C++, Python and C#

Watch it animatedStep through it, with the running line highlighted. Free with an account.

The idea

dp[i] is the length of the longest increasing subsequence that ends at index i. Any earlier smaller value a[j] can come right before a[i], extending its subsequence by one.

Code

C++PythonC#

int lengthOfLis(const vector<int>& a) {
    vector<int> dp(a.size(), 1);
    for (int i = 1; i < (int)a.size(); i++)
        for (int j = 0; j < i; j++)
            if (a[j] < a[i])
                dp[i] = max(dp[i], dp[j] + 1);
    return *max_element(dp.begin(), dp.end());
}

def length_of_lis(a: list[int]) -> int:
    dp = [1] * len(a)
    for i in range(1, len(a)):
        for j in range(i):
            if a[j] < a[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

public static int LengthOfLis(int[] a) {
    var dp = new int[a.Length];
    Array.Fill(dp, 1);
    for (int i = 1; i < a.Length; i++)
        for (int j = 0; j < i; j++)
            if (a[j] < a[i])
                dp[i] = Math.Max(dp[i], dp[j] + 1);
    return dp.Max();
}

Tips

The answer is the largest dp value, not the last one.
An O(n log n) version keeps a sorted "tails" list and uses binary search to place each value.

In the .NET library

dp.Max() is LINQ. For the O(n log n) version, List<T>.BinarySearch finds the position in the tails list.