Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 49
Good morning! Here's your coding interview problem for today.

This problem was asked by Amazon.

Given an array of numbers, find the maximum sum of any contiguous subarray of the array.

For example, given the array [34, -50, 42, 14, -5, 86], the maximum sum would be 137, since we would take elements 42, 14, -5, and 86.

Given the array [-5, -1, -8, -9], the maximum sum would be 0, since we would not take any elements.

Do this in O(N) time.



Pull request:
Day49
Resolves #107 .

Patch:
diff --git a/README.md b/README.md
index 158fb9b..3251678 100644
--- a/README.md
+++ b/README.md
@@ -60,3 +60,4 @@ problems from
 * [Day 45](https://github.com/vaskoz/dailycodingproblem-go/issues/101)
 * [Day 46](https://github.com/vaskoz/dailycodingproblem-go/issues/103)
 * [Day 47](https://github.com/vaskoz/dailycodingproblem-go/issues/105)
+* [Day 49](https://github.com/vaskoz/dailycodingproblem-go/issues/107)
diff --git a/day49/problem.go b/day49/problem.go
new file mode 100644
index 0000000..90f158a
--- /dev/null
+++ b/day49/problem.go
@@ -0,0 +1,20 @@
+package day49
+
+// MaxSubArray returns the maximum possible sum of a contiguous sub-array.
+// Runs in O(N) time and O(1) space.
+func MaxSubArray(arr []int) int {
+	var maxEndingHere, maxSoFar int
+	for i := range arr {
+		maxEndingHere = max(arr[i], maxEndingHere+arr[i])
+		maxSoFar = max(maxSoFar, maxEndingHere)
+	}
+	return maxSoFar
+}
+
+// max returns the larger of two ints.
+func max(a, b int) int {
+	if a > b {
+		return a
+	}
+	return b
+}


Test patch:
diff --git a/day49/problem_test.go b/day49/problem_test.go
new file mode 100644
index 0000000..6d71d50
--- /dev/null
+++ b/day49/problem_test.go
@@ -0,0 +1,28 @@
+package day49
+
+import "testing"
+
+var testcases = []struct {
+	arr    []int
+	maxSum int
+}{
+	{[]int{34, -50, 42, 14, -5, 86}, 137},
+	{[]int{-5, -1, -8, -9}, 0},
+}
+
+func TestMaxSubArray(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := MaxSubArray(tc.arr); result != tc.maxSum {
+			t.Errorf("Expected %d got %d", tc.maxSum, result)
+		}
+	}
+}
+
+func BenchmarkMaxSubArray(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			MaxSubArray(tc.arr)
+		}
+	}
+}