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