Skip to content

Algorithm for Longest Increasing Subsequence #27

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 1 commit into from
May 23, 2016
Merged

Algorithm for Longest Increasing Subsequence #27

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
1 commit
Select commit
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
3 changes: 2 additions & 1 deletion algorithm/etc/dp/desc.json
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -10,6 +10,7 @@
"files": {
"fibonacci": "Fibonacci Sequence",
"sliding_window": "Finding the largest sum of three contiguous number",
"max_sum_path": "Finding the maximum sum in a path from (0, 0) to (N-1, M-1) when can only move to right or down"
"max_sum_path": "Finding the maximum sum in a path from (0, 0) to (N-1, M-1) when can only move to right or down",
"longest_increasing_subsequence": "Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order"
}
}
31 changes: 31 additions & 0 deletions algorithm/etc/dp/longest_increasing_subsequence/code.js
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -0,0 +1,31 @@
tracer._pace(500);

// Initialize LIS values for all indexes
for( var i = 0; i < 20; i++) {
LIS[i] = 1;
}

tracer._print( 'Calculating Longest Increasing Subsequence values in bottom up manner ');
// Compute optimized LIS values in bottom up manner
for( var i = 1; i < 10; i++) {
tracer._select(i) ;
tracer._print( ' LIS['+i+'] = ' + LIS[i]);
for( var j =0; j < i; j++) {
tracer._notify(j);
if( A[i] > A[j] && LIS[i] < LIS[j] + 1) {
LIS[i] = LIS[j] + 1;
tracer._print( ' LIS['+i+'] = ' + LIS[i]);
}
}
tracer._deselect(i);
}

// Pick maximum of all LIS values
tracer._print( 'Now calculate maximum of all LIS values ');
var max = LIS[0];
for( var i = 1; i < 10; i++) {
if(max < LIS[i]) {
max = LIS[i];
}
}
tracer._print('Longest Increasing Subsequence = max of all LIS = ' + max);
4 changes: 4 additions & 0 deletions algorithm/etc/dp/longest_increasing_subsequence/data.js
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -0,0 +1,4 @@
var tracer = new Array1DTracer();
var A = Array1D.random(10, 0, 10);
var LIS = new Array(10);
tracer._setData(A);