Algoritmo Dinamico per il Massimo Prodotto Scalare di Sottosequenze
Un problema affascinante di programmazione dinamica sfida i developer: dato due array di numeri, trovare sottosequenze della stessa lunghezza non vuote che massimizzino il prodotto scalare. Le sottosequenze mantengono l’ordine relativo degli elementi originali, senza alterare le posizioni.
Esempi Pratici
Con array [2,1,-2,5] e [3,0,-6], la scelta ottimale è [2,-2] e [3,-6], per un risultato di 18 grazie ai prodotti positivi dominanti. In caso di valori negativi come [-1,-1] e [1,1], il massimo ottenibile è -1, selezionando un solo elemento per ciascuno.
Approccio con Programmazione Dinamica
Si utilizza una tabella bidimensionale DP dove ogni cella dp[i][j] memorizza il massimo prodotto scalare possibile usando i primi i elementi del primo array e i primi j del secondo. Per ogni coppia di posizioni:
- Si può saltare l’elemento corrente del primo array.
- Oppure saltare quello del secondo.
- O includerli entrambi, aggiungendo il loro prodotto solo se migliora il risultato (confrontando con zero per evitare penalità).
Questa strategia gestisce numeri negativi e positivi, garantendo la soluzione ottimale in tempo O(m*n), con m e n limitati a 500 elementi.
Implementazioni in Java, C++ e TypeScript mostrano codice pulito e ottimizzato, ideale per colloqui tecnici e piattaforme come LeetCode.