longest increasing subsequence nlogn c++
Longest Increasing Subsequence in C++
To find the length of the Longest Increasing Subsequence (LIS) in an array, you can use the following approach:
Initialize an array
dp
of sizeN
with all elements set to 1. This array will store the length of the LIS ending at each index.Iterate over the array from left to right. For each element at index
i
, compare it with all the previous elements at indicesj
such that0 < j < i
. Ifarr[j] < arr[i]
, it means thatarr[i]
can be included in the LIS ending at indexi
. In that case, updatedp[i]
as1 + dp[j]
, wheredp[j]
represents the length of the LIS ending at indexj
.Find the maximum value in the
dp
array. This will give you the length of the longest increasing subsequence in the given array.
Here's the C++ code that implements the above approach:
#include <iostream>
#include <vector>
using namespace std;
int longestIncreasingSubsequence(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[j] < arr[i]) {
dp[i] = max(dp[i], 1 + dp[j]);
}
}
}
int maxLength = 0;
for (int i = 0; i < N; i++) {
maxLength = max(maxLength, dp[i]);
}
return maxLength;
}
int main() {
vector<int> arr = {3, 10, 2, 1, 20};
int length = longestIncreasingSubsequence(arr);
cout << "Length of the longest increasing subsequence: " << length << endl;
return 0;
}
This code will output:
Length of the longest increasing subsequence: 3
Let me know if you need further assistance!