Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 193
Good morning! Here's your coding interview problem for today.

This problem was asked by Affirm.

Given a array of numbers representing the stock prices of a company in chronological order, write a function that calculates the maximum profit you could have made from buying and selling that stock. You're also given a number fee that represents a transaction fee for each buy and sell transaction.

You must buy before you can sell the stock, but you can make as many transactions as you like.

For example, given `[1, 3, 2, 8, 4, 10]` and `fee = 2`, you should return `9`, since you could buy the stock at 1 dollar, and sell at 8 dollars, and then buy it at 4 dollars and sell it at 10 dollars. Since we did two transactions, there is a 4 dollar fee, so we have 7 + 6 = 13 profit minus 4 dollars of fees.

Pull request description:
Day193
Resolves #399.

Patch:
diff --git a/README.md b/README.md
index ce37247..4fbad7a 100644
--- a/README.md
+++ b/README.md
@@ -203,6 +203,7 @@ problems from
 * [Day 190](https://github.com/vaskoz/dailycodingproblem-go/issues/393)
 * [Day 191](https://github.com/vaskoz/dailycodingproblem-go/issues/395)
 * [Day 192](https://github.com/vaskoz/dailycodingproblem-go/issues/397)
+* [Day 193](https://github.com/vaskoz/dailycodingproblem-go/issues/399)
 * [Day 194](https://github.com/vaskoz/dailycodingproblem-go/issues/400)
 * [Day 195](https://github.com/vaskoz/dailycodingproblem-go/issues/401)
 * [Day 196](https://github.com/vaskoz/dailycodingproblem-go/issues/404)
diff --git a/day193/problem.go b/day193/problem.go
new file mode 100644
index 0000000..a1f1cce
--- /dev/null
+++ b/day193/problem.go
@@ -0,0 +1,23 @@
+package day193
+
+// MaxProfitWithFee returns the maximum possible profit
+// by making transactions where each one has a fee.
+// A backtracking algorithm that tries all profitable paths
+// looking for the most profitable.
+func MaxProfitWithFee(prices []int, fee int) int {
+	if len(prices) < 2 {
+		return 0
+	}
+	buy := prices[0]
+	var maxProfit int
+	for i := 1; i < len(prices); i++ {
+		if prices[i] > buy+fee {
+			thisTradeProfit := prices[i] - buy - fee
+			totalProfit := thisTradeProfit + MaxProfitWithFee(prices[i+1:], fee)
+			if totalProfit > maxProfit {
+				maxProfit = totalProfit
+			}
+		}
+	}
+	return maxProfit
+}


Test patch:
diff --git a/day193/problem_test.go b/day193/problem_test.go
new file mode 100644
index 0000000..063f917
--- /dev/null
+++ b/day193/problem_test.go
@@ -0,0 +1,31 @@
+package day193
+
+import (
+	"reflect"
+	"testing"
+)
+
+var testcases = []struct {
+	prices    []int
+	fee       int
+	maxProfit int
+}{
+	{[]int{1, 3, 2, 8, 4, 10}, 2, 9},
+}
+
+func TestMaxProfitWithFee(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := MaxProfitWithFee(tc.prices, tc.fee); !reflect.DeepEqual(tc.maxProfit, result) {
+			t.Errorf("Expected %v, got %v", tc.maxProfit, result)
+		}
+	}
+}
+
+func BenchmarkMaxProfitWithFee(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			MaxProfitWithFee(tc.prices, tc.fee)
+		}
+	}
+}