## Uber Interview Question

Software Developers**Country:**India

**Interview Type:**Phone Interview

```
package main
import "fmt"
// Given an array of integers find the maximum value of
// a[i] - a[j] + a[k]
// with constraints
// i < j < k and a[i] < a[j] < a[k]
func main() {
a := []int{1, 3, 4, 5, 4}
max := 0 // Will return 0 if the matching combination is never found
for i := 0; i < len(a)-2; i++ {
for j := i + 1; j < len(a)-1; j++ {
for k := j + 1; k < len(a); k++ {
if a[i] < a[j] && a[j] < a[k] && max < a[i]-a[j]+a[k] {
max = a[i] - a[j] + a[k]
}
}
}
}
// O(n^3)
fmt.Printf("Max is %d\n", max)
// Optimization
lookup := make([]int, len(a))
m := a[len(a)-1]
lookup[len(a)-1] = m
for i := len(a) - 2; i > 0; i-- {
if m < a[i] {
m = a[i]
}
lookup[i] = m
}
fmt.Printf("Lookip is %v\n", lookup)
max = 0
for i := 0; i < len(a)-2; i++ {
for j := i + 1; j < len(a)-1; j++ {
if a[i] < a[j] && a[j] < lookup[j+1] && max < a[i]-a[j]+lookup[j+1] {
max = a[i] - a[j] + lookup[j+1]
}
}
}
// O(n^2) + S(n)
fmt.Printf("Max is %d\n", max)
}
```

- Ilya August 02, 2019