MaxSubArray mit dynamischem Stil

Question

Ich habe versucht, Code zu erstellen, der die maximale Teilzeichenfolge von Array zählt und Summe und Anfangs- und Endpunkt zurückgibt. Ich habe einen Fehler dort aber, dass ich nicht erkennen kann, zum Beispiel, wenn ich Array(-2, 1, -3, 4, -1, 2, 1, -5, 4) als Quelle verwende, bekomme ich zurück (7, 5,8). Die richtige Antwort sollte jedoch (6, 3, 6) sein. Code unten.

def solve(a: Array[Int]): (Int, Int, Int) = { 
    require(a.nonEmpty) 

    val n = a.length 
    val temp = Array.fill(n)(0, 0, 0) 
    var max = (0,0,0)      // sum, start, end 

    for (i <- 0 to n-1) { 
     temp(i) = (a(i), i, i) 
    } 

    for (i <- 0 to n-1) { 
     for (j <- 0 to i) { 
     if (a(i) > a(j) && temp(i)._1 < temp (j)._1 + a(i)) { 
      temp(i) = (temp(j)._1 + a(i), j, i) 
     } 
     } 
    } 
    for (i <- 0 to n-1){ 
     if (max._1 < temp(i)._1){ 
     max = temp(i)  
     } 
    } 
    return max 

} 

Answer 1

Wie wäre es mit einem Scala/funktionalen Ansatz?

def solve(a: Array[Int]): (Int, Int, Int) = { 
    a.tails.zipWithIndex.flatMap{ 
     case (arr, ti) => 
     arr.inits.map{ 
      tail => (tail.sum, ti, ti + tail.length -1) 
     } 
    }.maxBy(_._1) 
    } 

solve (Array(-2, 1, -3, 4, -1, 2, 1, -5, 4)) => res7: (Int, Int, Int) = (6,3,6)