Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 75
Good morning! Here's your coding interview problem for today.

This problem was asked by Microsoft.

Given an array of numbers, find the length of the longest increasing subsequence in the array. The subsequence does not necessarily have to be contiguous.

For example, given the array `[0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]`, the longest increasing subsequence has length 6: it is `0, 2, 6, 9, 11, 15`.

Pull request description:
Day75
Resolves #159.

Patch:
diff --git a/README.md b/README.md
index a8d7631..fa8dc51 100644
--- a/README.md
+++ b/README.md
@@ -84,3 +84,4 @@ problems from
 * [Day 72](https://github.com/vaskoz/dailycodingproblem-go/issues/153)
 * [Day 73](https://github.com/vaskoz/dailycodingproblem-go/issues/155)
 * [Day 74](https://github.com/vaskoz/dailycodingproblem-go/issues/157)
+* [Day 75](https://github.com/vaskoz/dailycodingproblem-go/issues/159)
diff --git a/day75/problem.go b/day75/problem.go
new file mode 100644
index 0000000..3beb65b
--- /dev/null
+++ b/day75/problem.go
@@ -0,0 +1,39 @@
+package day75
+
+// LongestIncreasingSubsequence returns the longest increasing subsequence.
+// Runs in O(N log N) time.
+func LongestIncreasingSubsequence(X []int) []int {
+	p := make([]int, len(X))
+	m := make([]int, len(X)+1)
+	l := 0
+	for i := range X {
+		lo := 1
+		hi := l
+		for lo <= hi {
+			var mid int
+			if (lo+hi)%2 == 0 {
+				mid = (lo + hi) / 2
+			} else {
+				mid = ((lo + hi) / 2) + 1
+			}
+			if X[m[mid]] < X[i] {
+				lo = mid + 1
+			} else {
+				hi = mid - 1
+			}
+		}
+		newL := lo
+		p[i] = m[newL-1]
+		m[newL] = i
+		if newL > l {
+			l = newL
+		}
+	}
+	s := make([]int, l)
+	k := m[l]
+	for i := range s {
+		s[len(s)-1-i] = X[k]
+		k = p[k]
+	}
+	return s
+}


Test patch:
diff --git a/day75/problem_test.go b/day75/problem_test.go
new file mode 100644
index 0000000..b7e0f60
--- /dev/null
+++ b/day75/problem_test.go
@@ -0,0 +1,30 @@
+package day75
+
+import (
+	"reflect"
+	"testing"
+)
+
+var testcases = []struct {
+	input, expected []int
+}{
+	{[]int{0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15},
+		[]int{0, 2, 6, 9, 11, 15}},
+}
+
+func TestLongestIncreasingSubsequence(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := LongestIncreasingSubsequence(tc.input); !reflect.DeepEqual(tc.expected, result) {
+			t.Errorf("Expected %v got %v", tc.expected, result)
+		}
+	}
+}
+
+func BenchmarkLongestIncreasingSubsequence(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			LongestIncreasingSubsequence(tc.input)
+		}
+	}
+}