Given an array of n positive integers. We need to find the largest increasing sequence of consecutive positive integers.

Examples:

Input : arr[] = {5, 7, 6, 7, 8} Output : Size of LIS = 4 LIS = 5, 6, 7, 8 Input : arr[] = {5, 7, 8, 7, 5} Output : Size of LIS = 2 LIS = 7, 8

This problem can be solved easily by the concept of LIS where each next greater element differ from earlier one by 1. But this will take O(n^2) time complexity.

With the use of hashing we can finding the size of longest increasing sequence with consecutive integers in time complexity of O(n).

We create a hash table.. Now for each element arr[i], we perform hash[arr[i]] = hash[arr[i] – 1] + 1. So, for every element we know longest consecutive increasing subsequence ending with it. Finally we return maximum value from hash table.

`// C++ implementation of longest continuous increasing ` `// subsequence ` `#include <bits/stdc++.h> ` `using` `namespace` `std; ` ` ` `// Function for LIS ` `int` `findLIS(` `int` `A[], ` `int` `n) ` `{ ` ` ` `unordered_map<` `int` `, ` `int` `> hash; ` ` ` ` ` `// Initialize result ` ` ` `int` `LIS_size = 1; ` ` ` `int` `LIS_index = 0; ` ` ` ` ` `hash[A[0]] = 1; ` ` ` ` ` `// iterate through array and find ` ` ` `// end index of LIS and its Size ` ` ` `for` `(` `int` `i = 1; i < n; i++) { ` ` ` `hash[A[i]] = hash[A[i] - 1] + 1; ` ` ` `if` `(LIS_size < hash[A[i]]) { ` ` ` `LIS_size = hash[A[i]]; ` ` ` `LIS_index = A[i]; ` ` ` `} ` ` ` `} ` ` ` ` ` `// print LIS size ` ` ` `cout << ` `"LIS_size = "` `<< LIS_size << ` ```
"
"
``` `; ` ` ` ` ` `// print LIS after setting start element ` ` ` `cout << ` `"LIS : "` `; ` ` ` `int` `start = LIS_index - LIS_size + 1; ` ` ` `while` `(start <= LIS_index) { ` ` ` `cout << start << ` `" "` `; ` ` ` `start++; ` ` ` `} ` `} ` ` ` `// driver ` `int` `main() ` `{ ` ` ` `int` `A[] = { 2, 5, 3, 7, 4, 8, 5, 13, 6 }; ` ` ` `int` `n = ` `sizeof` `(A) / ` `sizeof` `(A[0]); ` ` ` `findLIS(A, n); ` ` ` `return` `0; ` `} ` |

Output:

LIS_size = 5 LIS : 2 3 4 5 6

## leave a comment

## 0 Comments