C++ Program to Find Longest Increasing Subsequence

You can find the longest increasing subsequence in C++ by using dynamic programming with vector dp to store lengths and updating it with nested loops; for example, use for (int i = 1; i < n; i++) for (int j = 0; j < i; j++) if (arr[i] > arr[j]) dp[i] = max(dp[i], dp[j] + 1); and then find the maximum in dp.

Examples

Input10 22 9 33 21 50 41 60 80

Output6

Input3 10 2 1 20

Output3

Input3 2

Output1

How to Think About It

To find the longest increasing subsequence, think of checking each number and seeing if it can extend a smaller subsequence before it. We keep track of the longest subsequence length ending at each position by comparing current number with all previous numbers and updating lengths accordingly.

Algorithm

1

Get input array and its size.

2

Create a dp array of the same size, initialize all values to 1.

3

For each element from second to last, check all previous elements.

4

If current element is greater than a previous element, update dp[current] to max(dp[current], dp[previous] + 1).

5

Find and return the maximum value in dp array as the length of longest increasing subsequence.

Code

cpp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

int main() {
    vector<int> arr = {10, 22, 9, 33, 21, 50, 41, 60, 80};
    cout << longestIncreasingSubsequence(arr) << endl;
    return 0;
}

Output

6

Dry Run

Let's trace the example array [10, 22, 9, 33, 21, 50, 41, 60, 80] through the code.

1

Initialize dp array

dp = [1, 1, 1, 1, 1, 1, 1, 1, 1]

2

i=1, check j=0

arr[1]=22 > arr[0]=10, dp[1] = max(1, 1+1) = 2

3

i=2, check j=0,1

arr[2]=9 not > 10 or 22, dp[2] stays 1

4

i=3, check j=0..2

arr[3]=33 > 10, dp[3]=max(1,1+1)=2; >22 dp[3]=max(2,2+1)=3; >9 dp[3]=max(3,1+1)=3

5

Continue for i=4 to 8 updating dp

dp updates to [1,2,1,3,2,4,4,5,6]

6

Find max in dp

max_element(dp) = 6

i	dp array after updates
0	[1, 1, 1, 1, 1, 1, 1, 1, 1]
1	[1, 2, 1, 1, 1, 1, 1, 1, 1]
2	[1, 2, 1, 1, 1, 1, 1, 1, 1]
3	[1, 2, 1, 3, 1, 1, 1, 1, 1]
4	[1, 2, 1, 3, 2, 1, 1, 1, 1]
5	[1, 2, 1, 3, 2, 4, 1, 1, 1]
6	[1, 2, 1, 3, 2, 4, 4, 1, 1]
7	[1, 2, 1, 3, 2, 4, 4, 5, 1]
8	[1, 2, 1, 3, 2, 4, 4, 5, 6]

Why This Works

Step 1: Initialize dp array

Each position in dp starts at 1 because the smallest increasing subsequence ending at any element is the element itself.

Step 2: Compare elements

For each element, we check all previous elements to see if we can extend an increasing subsequence by adding the current element.

Step 3: Update dp values

If current element is greater than a previous one, we update dp[i] to the maximum length found so far plus one.

Step 4: Find maximum length

The longest increasing subsequence length is the maximum value in the dp array after processing all elements.

Alternative Approaches

Binary Search Optimization

cpp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

int main() {
    vector<int> arr = {10, 22, 9, 33, 21, 50, 41, 60, 80};
    cout << lengthOfLIS(arr) << endl;
    return 0;
}

This method uses binary search to build a subsequence array and runs in O(n log n) time, faster than the O(n^2) DP approach but is more complex to understand.

Recursive with Memoization

cpp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int lisHelper(const vector<int>& arr, int prevIndex, int curPos, vector<vector<int>>& memo) {
    if (curPos == arr.size()) return 0;
    if (memo[prevIndex + 1][curPos] != -1) return memo[prevIndex + 1][curPos];
    int taken = 0;
    if (prevIndex < 0 || arr[curPos] > arr[prevIndex])
        taken = 1 + lisHelper(arr, curPos, curPos + 1, memo);
    int notTaken = lisHelper(arr, prevIndex, curPos + 1, memo);
    memo[prevIndex + 1][curPos] = max(taken, notTaken);
    return memo[prevIndex + 1][curPos];
}

int longestIncreasingSubsequence(const vector<int>& arr) {
    vector<vector<int>> memo(arr.size() + 1, vector<int>(arr.size(), -1));
    return lisHelper(arr, -1, 0, memo);
}

int main() {
    vector<int> arr = {10, 22, 9, 33, 21, 50, 41, 60, 80};
    cout << longestIncreasingSubsequence(arr) << endl;
    return 0;
}

This recursive method with memoization is easier to understand conceptually but less efficient than the binary search approach.

Complexity: O(n^2) time, O(n) space

Time Complexity

The nested loops cause the time to grow roughly with the square of the input size, as each element is compared with all previous elements.

Space Complexity

The dp array uses extra space proportional to the input size to store subsequence lengths.

Which Approach is Fastest?

The binary search method runs in O(n log n) and is faster for large inputs, but the O(n^2) DP approach is simpler and easier to understand.

Approach	Time	Space	Best For
Dynamic Programming	O(n^2)	O(n)	Small to medium inputs, easy to understand
Binary Search Optimization	O(n log n)	O(n)	Large inputs, performance critical
Recursive with Memoization	O(n^2)	O(n^2)	Conceptual clarity, smaller inputs