Rangetree3, la seconda richiesta


#1

Sto cercando di risolvere il terzo problema sui rangetree Can you answer these queries III ( rangetree3 ), e la seconda operazione richiesta dal problema non mi è chiara.
Pensavo che richiedesse la somma massima nel range dato in input, ma nella seconda query dopo la modifica restitusice 4.
Altro disegnigno brutto sempre fatto da me ^-^


Ho aperto un nuovo thread perché mi sembrava esagerato riaprire uno del 2014 <.<


#2

Ciao, la seconda operazione richiede la massima somma di valori adiacenti all’interno dell’intervallo.
Nel caso dell’operazione q(2,4) le possibili somme sono:

  • 2 = 2
  • -3 = -3
  • 4 = 4
  • 2-3 = -1
  • -3+4 = 1
  • 2-3+4 = 3

In questo caso la somma massima è 4. Non si può ottenere la somma di 2 e 4 perché i due valori non sono adiacenti.
Questo è lo stesso problema (senza la parte degli update): https://en.wikipedia.org/wiki/Maximum_subarray_problem


#3

Grazie mille della spiegazione, ora provo a risolverlo.


#4

Tra l’altro sarebbe carino diminuire i limiti di tempo / sistemare gli input perché è possibile prendere 100 punti con una soluzione O(NM) :sweat_smile: