Rangetree3, la seconda richiesta

[zJack1342]

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 <.<

[tpoppo]

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

[zJack1342]

Grazie mille della spiegazione, ora provo a risolverlo.

[filippos]

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