Runtime Exceeded for Best Time to Buy and Sell Stock 3

This is my code for leetcode problem - Best Time to Buy and Sell Stock 3
and my Golang code passes 203/214 test cases. My time limit gets exceeded for a particular input array of size 10k. Any ideas?

By basic algorithm goes as follows :-

1. Find indices till where the price is decreasing and ignore all elements before it. For eg if an array goes like [5,4,3,2,1,2,3,4], here the price is decreasing till the 4th index.
2. Find all local minimas and local maximas. Because you wouldn't wanna buy unless it's a local minima likewise for selling
3. If there's only one profitable transaction, i.e. only one local min and one local max, return that.
4. Find all profitable transaction pairs by checking for all permutations for buying at a local min and selling at a local max.
5. Return the highest transaction pair

My code :

func maxProfit(prices []int) int {
//trim left
temp, i := 0, 1
for ; i < len(prices) && prices[i] <= prices[temp]; i += 1 {
temp = i
}
if i == len(prices) {
return 0
}
i -= 1
//find all local lows and highs
localLows := []int{i}
localHighs := []int{}
for j := i + 1; j < len(prices)-1; j += 1 {
if prices[j] >= prices[j+1] {
for prices[j] == prices[j+1] {
j += 1
if j == len(prices)-1 {
break
}
}
localHighs = append(localHighs, j)
for ; j < len(prices)-1 && prices[j] >= prices[j+1]; j++ {
fmt.Print(j, " j")
}
fmt.Println()
localLows = append(localLows, j)
}
}
if prices[len(prices)-1] > prices[len(prices)-2] {
localHighs = append(localHighs, len(prices)-1)
}
fmt.Println(localLows, localHighs)
//if only one transaction, return that
if len(localHighs) == 1 {
return prices[localHighs[0]] - prices[localLows[0]]
}
//find all profitable transaction pairs
maxProfit := 0
for j := 0; j < len(localHighs); j += 1 {
for k := j; k < len(localHighs); k += 1 {
if prices[localHighs[k]]<prices[localLows[j]]{
continue
}
transaction1 := int(prices[localHighs[k]] - prices[localLows[j]])
for l := k + 1; l < len(localHighs); l++ {
for m := l; m < len(localHighs); m++ {
if prices[localHighs[m]]<prices[localLows[l]]{
continue
}
transaction2 := int(prices[localHighs[m]] - prices[localLows[l]])
// fmt.Println(localLows[j], localHighs[k], localLows[l], localHighs[m])
if (transaction1 + transaction2) > maxProfit {
maxProfit = transaction1 + transaction2
}
}
}
}
}
return maxProfit
}

Did you consider the fact that your approach is good BUT crucially however not good enough for Leetcode ? I had a hard time understanding how the state machine equations work but after spending a lot of time thinking about it, I finally understood it.

This is the working code for that approach.

func getMin(v1 int, v2 int) int {
if v1 < v2 {
return v1
}
return v2
}
func getMax(v1 int, v2 int) int {
if v1 > v2 {
return v1
}
return v2
}
func maxProfit(prices []int) int {    
var cp1, cp2, mp1, mp2 int
cp1 = math.MaxInt
cp2 = math.MaxInt
mp1 = 0 
mp2 = 0
for i:= 0; i < len(prices); i++ {
cp1 = getMin(cp1, prices[i])
mp1 = getMax(mp1, prices[i]-cp1)
cp2 = getMin(cp2, prices[i]-mp1)
mp2 = getMax(mp2, prices[i]-cp2)
}
return mp2
}

cp1 is the cost price for the 1st transaction.
mp1 is the maximum profit for the 1st transaction.

If this problem only asked for the maximum profit from a single transaction, the solution ends right here and in fact that's the easy version of this problem.

Since we have the option to execute another transaction albeit one which doesn't overlap with the previous transaction, we go ahead and define cp2, mp2.

cp2 and mp2 are basically the same as cp1 and mp1 except for the fact that cp2 i.e. cost price 2 or cost price for the 2nd transaction can be potentially less than the price[i] for that given day.

Why exactly is it less ?
This is because if we made some profit from the 1st transaction then we could use that profit to offset or reduce the the 2nd cost price, which is why I'm subtracting the profit mp1 from cp2.

cp2 = getMin(cp2, prices[i]-mp1)

Think about it, if you made a profit of USD 100 from some transaction today in the stock market around 9 AM and did nothing afterwards, when you go in for your 2nd transaction to buy something for say USD 250 later in the day around 11AM, you could say that you bought it for USD 150 (because you made a profit of USD 100 earlier in the day). It's the same thing here. If you wind up selling this for USD 350, that means you've made a total profit of USD 200 ( either you could say USD350-USD150 OR USD250-USD150 + (USD 100 of 1st transaction, both mean the same)