Merge pull request algorithm-visualizer#27 from archie94/longestIncreasingSubsequence

64json · 64json · commit 58473b3fb06e · 2016-05-23T12:59:18.000-05:00
Algorithm for Longest Increasing Subsequence
diff --git a/algorithm/etc/dp/desc.json b/algorithm/etc/dp/desc.json
@@ -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"
   }
 }
diff --git a/algorithm/etc/dp/longest_increasing_subsequence/code.js b/algorithm/etc/dp/longest_increasing_subsequence/code.js
@@ -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);
diff --git a/algorithm/etc/dp/longest_increasing_subsequence/data.js b/algorithm/etc/dp/longest_increasing_subsequence/data.js
@@ -0,0 +1,4 @@
+var tracer = new Array1DTracer();
+var A = Array1D.random(10, 0, 10);
+var LIS = new Array(10);
+tracer._setData(A);

Original file line number	Diff line number	Diff line change
`@@ -10,6 +10,7 @@`
`10`	`10`	`"files": {`
`11`	`11`	`"fibonacci": "Fibonacci Sequence",`
`12`	`12`	`"sliding_window": "Finding the largest sum of three contiguous number",`
`13`		`- "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"`
	`13`	`+ "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",`
	`14`	`+ "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"`
`14`	`15`	`}`
`15`	`16`	`}`