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 :-
- 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.
- Find all local minimas and local maximas. Because you wouldn't wanna buy unless it's a local minima likewise for selling
- If there's only one profitable transaction, i.e. only one local min and one local max, return that.
- Find all profitable transaction pairs by checking for all permutations for buying at a local min and selling at a local max.
- 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
}