Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 190
Good morning! Here's your coding interview problem for today.

This problem was asked by Facebook.

Given a circular array, compute its maximum subarray sum in O(n) time.

For example, given `[8, -1, 3, 4]`, return `15` as we choose the numbers `3, 4, and 8` where the `8` is obtained from wrapping around.

Given `[-4, 5, 1, 0]`, return `6` as we choose the numbers `5 and 1`.

Pull request description:
Day190
Resolves #393.

Patch:
diff --git a/README.md b/README.md
index 8064228..6ce3b31 100644
--- a/README.md
+++ b/README.md
@@ -200,3 +200,4 @@ problems from
 * [Day 187](https://github.com/vaskoz/dailycodingproblem-go/issues/387)
 * [Day 188](https://github.com/vaskoz/dailycodingproblem-go/issues/388)
 * [Day 189](https://github.com/vaskoz/dailycodingproblem-go/issues/391)
+* [Day 190](https://github.com/vaskoz/dailycodingproblem-go/issues/393)
diff --git a/day190/problem.go b/day190/problem.go
new file mode 100644
index 0000000..a7376fe
--- /dev/null
+++ b/day190/problem.go
@@ -0,0 +1,34 @@
+package day190
+
+// MaxWrapSubarraySum returns the maximum possible sum for
+// a subarray in a circular array.
+// Runs in O(N) time and O(N) space because the data is mutated.
+func MaxWrapSubarraySum(nums []int) int {
+	data := make([]int, len(nums))
+	copy(data, nums)
+	maxKadane := KadaneAlg(data)
+	maxWrap := 0
+	for i, v := range data {
+		maxWrap += v
+		data[i] = -data[i]
+	}
+	maxWrap += KadaneAlg(data)
+	return max(maxWrap, maxKadane)
+}
+
+// KadaneAlg implements https://en.wikipedia.org/wiki/Maximum_subarray_problem#Kadane's_algorithm
+func KadaneAlg(nums []int) int {
+	maxEndingHere, maxSoFar := nums[0], nums[0]
+	for i := 1; i < len(nums); i++ {
+		maxEndingHere = max(nums[i], maxEndingHere+nums[i])
+		maxSoFar = max(maxSoFar, maxEndingHere)
+	}
+	return maxSoFar
+}
+
+func max(a, b int) int {
+	if a > b {
+		return a
+	}
+	return b
+}


Test patch:
diff --git a/day190/problem_test.go b/day190/problem_test.go
new file mode 100644
index 0000000..3970bd3
--- /dev/null
+++ b/day190/problem_test.go
@@ -0,0 +1,28 @@
+package day190
+
+import "testing"
+
+var testcases = []struct {
+	nums   []int
+	maxSum int
+}{
+	{[]int{8, -1, 3, 4}, 15},
+	{[]int{-4, 5, 1, 0}, 6},
+}
+
+func TestMaxWrapSubarraySum(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := MaxWrapSubarraySum(tc.nums); result != tc.maxSum {
+			t.Errorf("Expected %v, got %v", tc.maxSum, result)
+		}
+	}
+}
+
+func BenchmarkMaxWrapSubarraySum(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			MaxWrapSubarraySum(tc.nums)
+		}
+	}
+}