Increasing Subsequence

You are given an array containing n integers. Your task is to determine the longest increasing subsequence in the array, i.e., the longest subsequence where every element is larger than the previous one.

A subsequence is a sequence that can be derived from the array by deleting some elements without changing the order of the remaining elements.

Example:

Input:  n = 8, a = {7, 3, 5, 3, 6, 2, 9, 8}
Output: 4

Approach

C++

#include <bits/stdc++.h>
using namespace std;

int increasingSubsequnce(int n, vector<int> &a)
{

    vector<int> dp;
    for (int i = 0; i < n; i++)
    {
        auto it = lower_bound(dp.begin(), dp.end(), a[i]);
        if (it == dp.end())
            dp.push_back(a[i]);
        else
            *it = a[i];
    }
    return dp.size();
}

int main()
{
    int n = 8;

    vector<int> a = {7, 3, 5, 3, 6, 2, 9, 8};

    cout << increasingSubsequnce(n, a) << "\n";

    return 0;
}