Problem

Given an array of integers, find the length of the longest increasing subsequence in the array.
Example input: [10, 9, 2, 5, 3, 7, 101, 18]
Example output: 4

Solution

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    vector<int> input = {10, 9, 2, 5, 3, 7, 101, 18};
    vector<int> dp(input.size(), 1);
    int max_len = 1;
    for (int i = 1; i < input.size(); i++) {
        for (int j = 0; j < i; j++) {
            if (input[i] > input[j]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        max_len = max(max_len, dp[i]);
    }
    cout << max_len << endl;
    return 0;
}

/*

The solution is optimal because it uses dynamic programming to solve the problem.

The solution is O(n^2) because it uses two for loops.

*/