Method 1) Brute Force Approch
for (i=N; i>0 ; –i){
Find a SubSequence of length i
if any increasing subsequence
Break;
}
But finding all subsequence of length i will give Time Complexity in Exponential.
as all subsequences will be N! / i! * (N-i)!
Lets think directly in DP way…
Method 2) Dynamic Programming way.
Take Example D := { 3, 2 , 6 , 4 , 5 , 1 } We are defining vector L of vector <Numbers> such that
L[i] = A vector, Longest Increasing sequence of D that ends with D[i].
L[0] = 3.
L[1] = 2 ( because 3 > 2, and we need to find increasing sub sequence )
L[2] = 2,6
L[3] = 2,4
L[4] = 2,4,5
L[5] = 1
say L[2] = 2,6 is ‘2’ + ‘6’ where 2 is so far found max LIS, and ‘6’ is current element
So formula
L[i] is maximum of all L[j] where j<i and D[j]<D[i] + ‘D[i]’
L[i] = MAX(L[j], where j<i, D[j]<D[i]) + D[i]
So now We have working code to print all Increasing SubSequence
Edit it your way to find larget increasing subsequence
Code :
#include <iostream>
using namespace std;
#include <iostream>
#include <vector>
void prt(vector<int>& arr, string msg = “”) {
cout << msg << ” “;
for (auto i: arr) {
cout << i << ” “;
}
cout << endl;
}
void calc_LIS(vector<int>& D) {
vector< vector<int> > L(D.size()); // The longest increasing subsequence ends with D[i]
L[0].push_back(D[0]);
for (int i=1; i<D.size(); i++) {
for(int j=0; j<i; j++) {
if ( (D[j] < D[i]) && ( L[i].size() < L[j].size() ) ) {
L[i] = L[j];
}
}
L[i].push_back(D[i]);
}
for (auto x: L) {
prt(x);
}
}
int main() {
int a[] = {3, 2, 6, 4, 5, 1};
vector<int> arr(a, a + sizeof(a)/sizeof(a[0]));
//prt(arr, “Data In:”);
calc_LIS(arr);
return 0;
}
Working Code at : http://ideone.com/lOrktE