lis Algorithm
An algorithm is a step-by-step procedure or a set of rules and instructions to solve a particular problem or perform a specific task. The list algorithm, in the context of computer science and data structures, is a collection of techniques and methods designed to efficiently manage and manipulate lists. Lists are a fundamental data structure that store multiple elements in a linear order, allowing for easy access, addition, and removal of elements. List algorithms play a crucial role in various applications, such as sorting, searching, and merging, as they provide efficient ways to handle and process data in lists.
List algorithms can be implemented using different data structures such as arrays, linked lists, or dynamic arrays, and their efficiency may vary based on the chosen structure. Some well-known list algorithms include the binary search algorithm, which efficiently searches for a specific element in a sorted list; the merge sort algorithm, which is an efficient and stable sorting technique that divides a list into smaller sublists and combines them in a sorted order; and the quick sort algorithm, which is another sorting technique that selects a 'pivot' element and rearranges the list such that all elements less than the pivot come before it, and all elements greater than the pivot come after it. These algorithms, along with countless others, form the foundation of computer programming and data manipulation, enabling the development of complex software and applications.
#include <iostream>
#include <algorithm>
#include <vector>
const int INF = 2e9 + 10;
void printArray(std :: vector <int> arr){
std :: cout << '[';
const int n = arr.size();
for(int i = 0; i != n; ++ i){
if(i) std :: cout << ", ";
std :: cout << arr[i];
}
std :: cout << ']';
}
int LIS(std :: vector <int> arr){
const int n = arr.size() + 1;
int dp[n];
dp[0] = -INF;
for(int i = 1; i < n; ++ i){
dp[i] = INF;
}
int pos = 0;
for(int i = 0; i != n - 1; ++ i){
int cur = std :: upper_bound(dp, dp + n, arr[i]) - dp;
if(dp[cur] > arr[i]) dp[cur] = arr[i];
}
for(int i = 0; i != n; ++ i){
if(dp[i] == INF) break;
pos = i;
}
return pos;
}
int main(){
std :: vector <int> array = {3, 4, 5, 2, 6, 7};
std :: cout << "The Longest Increasing sequence of ";
printArray(array);
std :: cout << " is " << LIS(array);
return 0;
}
