cicli innestati in una mappa

[flyfly2301]

Buonasera. Ho una mappa (chiave, valore) in cui dovrei trovare l'intervallo delle chiavi i cui valori sommati sono massimi (alcuni valori della mappa sono negativi). Ho provato con questo doppio ciclo ma non mi viene fuori il valore corretto seppure il codice mi pare giusto. Dove sbaglio???

int time_def1 = 0;
int time_def2 = 0;
double dev_defin = 0;


for (int i = 0; i < map_deviation.size(); i++) {
int time_1 = indici.get(i);
double somma = map_deviation.get(time_1);
for (int j = i+1; j < map_deviation.size(); j++) {
int time_2 = indici.get(j);
double somma1 = somma + map_deviation.get(time_2);
if (somma1 > somma){
dev_defin = somma1;
time_def1 = time_1;
time_def2 = time_2;
}
somma = somma1;
}
}

System.out.println(time_def1 + ", " + time_def2 + ", " + dev_defin);

[andbin]

Dove sbaglio???

if (somma1 > somma){

Il problema è qui: stai confrontando la sommatoria di quel intervallo rispetto a quella appena precedente.
Il confronto va fatto rispetto dev_defin

[Scara95]

Comunque se è ordinata il problema si può risolvere in O(n):

  int seq[] = {1, -3, 5, 7, -1, 2 }; //out 2-5 13
  /*int seq[] = {-1, -3, -5, -7, -1, -2 }; 
    //out -1--1 0
    //nel caso si voglia lo stesso l'intervallo basta trovare il valore massimo 0-0 -1 o 4-4 -1
    //trovare il massimo è O(n) e quindi non cambia la complessità, inoltre puoi farlo all'interno del ciclo
  //*/
  int curr = 0, max = 0, start = -1, curr_start = 0, stop = -1;
  for(int i = 0; i < seq.length; ++i) {
   curr += seq[i];
   if(curr < 0) {
    curr_start = i+1;
    curr = 0;
   }
   else if(curr > max) {
    
    start = curr_start;
    stop = i;
    max = curr;
   }
  }
  System.out.println(""+start+"-"+stop+" "+max);

Edit: ah, il se è ordinata l'ho dato per scontato, altrimenti ovviamente sarebbe la somma dei soli valori positivi e quindi sarebbe O(n) comunque. (In questo caso più che un intervallo di indici sarebbe un set(?))

Edit1: è (curr >= max) altrimenti si ottiene quella massima ma non necessariamente più lunga (ovvero si possono scartare gli 0)

[flyfly2301]

Risolto grazie all'accorgimento di andbin, bastava modificare somma con dev_defin. Grazie mille a tutti.

[Scara95]

Risolto grazie all'accorgimento di andbin, bastava modificare somma con dev_defin. Grazie mille a tutti.

Resta comunque un O(n^2), su input piccoli non cambia molto ma se pensi di dover considerare input di una certa dimensione la differenza diventa considerevole.

Ciao, comunque