cicli innestati in una mappa

[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)