Longest Increasing Subsequence

The algorithm uses a dynamic array (lis) to keep track of the smallest possible values of increasing subsequences of different lengths.

Longest Increasing Subsequence (LIS) Using Binary Search

Key Idea:

• For each element in the array, use lower_bound to find the position where it can fit in lis (i.e., replace the first element that is not smaller than it).

• If it’s greater than all elements in lis, it’s appended to lis, extending the length of our potential LIS.

• At the end, the size of lis gives the length of the LIS.

Example Array

Let's take an example array:

vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};

Workflow Step-by-Step

1. Initialize lis:

   • Start with an empty vector lis that will hold the current smallest possible increasing subsequence.

2. Process Each Element:

   • For each number, perform the following:

   Step	Element	Action with lis (after lower_bound)	Resulting lis
   1	10	Add 10 (empty lis)	[10]
   2	9	Replace 10 with 9 (position 0)	[9]
   3	2	Replace 9 with 2 (position 0)	[2]
   4	5	Append 5 (position 1)	[2, 5]
   5	3	Replace 5 with 3 (position 1)	[2, 3]
   6	7	Append 7 (position 2)	[2, 3, 7]
   7	101	Append 101 (position 3)	[2, 3, 7, 101]
   8	18	Replace 101 with 18 (position 3)	[2, 3, 7, 18]

3. Result:

   • At the end, lis = [2, 3, 7, 18], and its length (4) is the length of the LIS for the input array.

Code

int lengthOfLIS(vector<int>& nums) {
    vector<int> lis;
    for (int x : nums) {
        auto it = lower_bound(lis.begin(), lis.end(), x);
        if (it == lis.end()) lis.push_back(x);
        else *it = x;
    }
    return lis.size();
}

int main() {
    vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
    cout << "Length of LIS: " << lengthOfLIS(nums) << endl;
    return 0;
}