We are given two arrays $a$ and $b$ of length $n$. Consider the following recurrence relation:↵
↵
$$f(i) = \displaystyle \min_{b[i]\; \leq\; j\; <\; i}\big\{f(j)+ \max(a[j+1], \dots, a[i])\big\}$$↵
↵
We are interested in calculating $f(n)$. Is there a way to calculate it with the time complexity being better than $\mathcal{O}(n^2)$?↵
↵
**UPD:** I forgot to mention that the array $b$ is monotone (ie $b[i] \leq b[i+1]$). Don't know if that helps though...
↵
$$f(i) = \displaystyle \min_{b[i]\; \leq\; j\; <\; i}\big\{f(j)+ \max(a[j+1], \dots, a[i])\big\}$$↵
↵
We are interested in calculating $f(n)$. Is there a way to calculate it with the time complexity being better than $\mathcal{O}(n^2)$?↵
↵
**UPD:** I forgot to mention that the array $b$ is monotone (ie $b[i] \leq b[i+1]$). Don't know if that helps though...
