Se observă că $inter[i][j]$ nu reprezintă altceva decât indicele $k$ tratat in paragraful precedent.
De asemenea, $inter$ poate fi calculată în $O(N^2)$ observând o proprietate simplă: <tex>$inter[i][j-1] \le inter[i][j] \le inter[i+1][j] $</tex>. Aceasta reiese imediat din monotonia lui $opt$ discutată mai sus.

Acum vine ideea decisivă pentru a reduce complexitatea loop-ului: pentru a afla $opt[i][j]$, este suficient să aflăm maximul dintre 2 valori:

Acum vine ideea decisivă pentru a reduce complexitatea loop-ului: pentru a afla $opt[i][j]$, este suficient să aflăm minimul dintre 2 valori:

* <tex>\displaystyle\min_{i \le k \le inter[i][j]} \{$to_left[k][j]$\} </tex> şi
* <tex>\displaystyle\min_{inter[i][j] < k \le j } \{$to_left[i][k]$\} </tex>

* <tex>\displaystyle\min_{i \le k \le inter[i][j]} \{$to\_left[k][j]$\} </tex> şi
* <tex>\displaystyle\min_{inter[i][j] < k \le j } \{$to\_right[i][k]$\} </tex>
Mai exact,
@opt[ i ][ j ]@ = <tex> \max( \displaystyle\min_{i \le k \le inter[i][j]} \{$to\_left[k][j]$\},
                              \displaystyle\min_{inter[i][j] < k \le j } \{$to\_right[i][k]$\} ) </tex>

h3(#problema-2). Problema 2: 'Ugly numbers':http://code.google.com/codejam/contest/dashboard?c=32015#s=p1&a=1 (Google Code Jam 2008, Round 1C)