This approach is better (O(n^2)) runtime. It is accepted by leetcode. It's not exactly simple though and the intuition for the memoization is a bit confusing.
(nums []int, prevIdx int, currentIdx int, memo [][]int)
| 58 | // It's not exactly simple though and the intuition for the |
| 59 | // memoization is a bit confusing. |
| 60 | func explore3(nums []int, prevIdx int, currentIdx int, memo [][]int) int { |
| 61 | if currentIdx == len(nums) { |
| 62 | return 0 |
| 63 | } |
| 64 | |
| 65 | if memo[prevIdx+1][currentIdx] >= 0 { |
| 66 | return memo[prevIdx+1][currentIdx] |
| 67 | } |
| 68 | |
| 69 | max1 := 0 |
| 70 | if prevIdx < 0 || nums[prevIdx] < nums[currentIdx] { |
| 71 | max1 = 1 + explore3(nums, currentIdx, currentIdx+1, memo) |
| 72 | } |
| 73 | |
| 74 | max2 := explore3(nums, prevIdx, currentIdx+1, memo) |
| 75 | memo[prevIdx+1][currentIdx] = int(math.Max(float64(max1), float64(max2))) |
| 76 | return memo[prevIdx+1][currentIdx] |
| 77 | } |
| 78 | |
| 79 | // This approach is also slow (O(2^n) runtime. |
| 80 | // It works, but times out on leetcode. |