4. The greatest substring algorithm is a used in a number of varying application

Question

4. The greatest substring algorithm is a used in a number of varying applications including visual recognition and molecular biology. Basically a string of values is processed and the LONGEST sequential substring that has the greatest subtotal is computed. For example: if VI3, -5, 2, 4, 2, -1, 5,-8 0 2] then the greatest substring is [2, 4, 3,-1, 5] with a total of 13. Accept from the keyboard a number N of random values [-20:20] and load them into the list V and display the contents. Process the list and load the solution into a separate data structure of your choice, display the contents.

Explanation / Answer

C++ Program: Using Hashing with a complexity of O(n)

The code is well documented with comments, following the code is sufficient for understanding

#include<iostream>

#include<vector>

#include<unordered_set>

using namespace std;

int findSubstring(vector<int> &vec) {

int n = vec.size();

unordered_set<int> s;

int ans = 0;

// Hash all the array elements

for (int i = 0; i < n; i++) {

s.insert(vec[i]);

}

// check each possible sequence from the start

// then update optimal length

for (int i = 0; i < n; i++)

{

// if current element is the starting

// element of a sequence

if (s.find(vec[i]-1) == s.end())

{

// Then check for next elements in the

// sequence

int j = vec[i];

while (s.find(j) != s.end())

j++;

// update optimal length if this length

// is more

ans = max(ans, j - vec[i]);

}

}

return ans;

}

int main() {

vector<int> seq;

int val;

int n;

cout << "Enter the total number elements in the sequence: ";

cin >> n;

cout << "Enter the sequence within a range of -20 to 20: ";

for(int i = 0; i < n; i++) {

cin >> val;

seq.push_back(val);

}

int result = findSubstring(seq);

cout << result;

return 0;

}

If we need to print the subsequence, we have to compromise with the time complexity by sorting the array which takes O(nlogn)

C++ Code for printing Longest Consecutive Subsequence is as follows:

#include<iostream>

#include<algorithm>

#include<vector>

using namespace std;

int main() {

vector<int> seq;

int val;

int n;

cout << "Enter the total number elements in the sequence: ";

cin >> n;

cout << "Enter the sequence within a range of -20 to 20: ";

for(int i = 0; i < n; i++) {

cin >> val;

seq.push_back(val);

}

sort(seq.begin(), seq.end());

int m = 1;

int length = 1;

vector<int> soln;

soln.push_back(seq[0]);

int flag = 0;

for(int i = 1; i < seq.size(); i++) {   

if(seq[i] == seq[i-1]+1) {

length++;

} else {

length = 1; flag = 1;

}

if(length > m && !flag) {

soln.push_back(seq[i]);

} else if(length > m && flag) {

flag = 0;

soln.clear();

cout << length << endl;

for(int k = length-1; k >= 0; k--) {

soln.push_back(seq[i-k]);

}

}

m = max(m, length);

}

cout << m;

for(int i = 0; i < soln.size(); i++) {

cout << soln[i] << " ";

}

}

Related Questions

Navigate

• Browse (All)
• Browse 4
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.