Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 9
Good morning! Here's your coding interview problem for today.

This problem was asked by Airbnb.

Given a list of integers, write a function that returns the largest sum of non-adjacent numbers. Numbers can be 0 or negative.

For example, [2, 4, 6, 2, 5] should return 13, since we pick 2, 6, and 5. [5, 1, 1, 5] should return 10, since we pick 5 and 5.

Follow-up: Can you do this in O(N) time and constant space?

Pull request description:
Day9
Resolves #19 

Patch:
diff --git a/README.md b/README.md
index 116080e..6f4b50b 100644
--- a/README.md
+++ b/README.md
@@ -18,3 +18,4 @@ problems from
 * [Day 6](https://github.com/vaskoz/dailycodingproblem-go/issues/13)
 * [Day 7](https://github.com/vaskoz/dailycodingproblem-go/issues/15)
 * [Day 8](https://github.com/vaskoz/dailycodingproblem-go/issues/17)
+* [Day 9](https://github.com/vaskoz/dailycodingproblem-go/issues/19)
diff --git a/day9/problem.go b/day9/problem.go
new file mode 100644
index 0000000..d5af376
--- /dev/null
+++ b/day9/problem.go
@@ -0,0 +1,26 @@
+package day9
+
+// MaximumNonAdjacentSum calculates the largest possible sum without using adjacent values.
+// Runs in O(N) time and O(1) space.
+func MaximumNonAdjacentSum(nums []int) int {
+	var one, two, result int
+	for i, val := range nums {
+		if i == 0 {
+			result = val
+		} else if i == 1 {
+			result = max(result, val)
+		} else {
+			result = max(one, val+two)
+		}
+		two = one
+		one = result
+	}
+	return result
+}
+
+func max(a, b int) int {
+	if a > b {
+		return a
+	}
+	return b
+}


Test patch:
diff --git a/day9/problem_test.go b/day9/problem_test.go
new file mode 100644
index 0000000..0c7cb21
--- /dev/null
+++ b/day9/problem_test.go
@@ -0,0 +1,28 @@
+package day9
+
+import "testing"
+
+var testcases = []struct {
+	input    []int
+	expected int
+}{
+	{[]int{2, 4, 6, 2, 5}, 13},
+	{[]int{5, 1, 1, 5}, 10},
+	{[]int{10, 1}, 10},
+}
+
+func TestMaximumNonAdjacentSum(t *testing.T) {
+	for _, tc := range testcases {
+		if result := MaximumNonAdjacentSum(tc.input); result != tc.expected {
+			t.Errorf("Expected %v, but got %v", tc.expected, result)
+		}
+	}
+}
+
+func BenchmarkMaximumNonAdjacentSum(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			MaximumNonAdjacentSum(tc.input)
+		}
+	}
+}