This approach is slow (exponential runtime). It works, but times out on leetcode. We can do better.
(nums []int)
| 97 | // It works, but times out on leetcode. |
| 98 | // We can do better. |
| 99 | func explore1(nums []int) int { |
| 100 | if len(nums) == 0 { |
| 101 | return 0 |
| 102 | } |
| 103 | |
| 104 | if isIncreasing(nums) { |
| 105 | return len(nums) |
| 106 | } |
| 107 | |
| 108 | maxLen := 0 |
| 109 | for i := range nums { |
| 110 | newNums := append(append([]int{}, nums[0:i]...), nums[i+1:]...) |
| 111 | if isIncreasing(newNums) { |
| 112 | return len(newNums) |
| 113 | } |
| 114 | |
| 115 | max := explore1(newNums) |
| 116 | if max > maxLen { |
| 117 | maxLen = max |
| 118 | } |
| 119 | } |
| 120 | |
| 121 | return maxLen |
| 122 | } |
| 123 | |
| 124 | func isIncreasing(nums []int) bool { |
| 125 | for i := 1; i < len(nums); i++ { |
nothing calls this directly
no test coverage detected