使用動態樣式的MaxSubArray

我一直在試圖創建代碼來計算數組中的最大子字符串並返回總和以及起點和終點。我在那裏有一些錯誤，但我不能發現，因爲例如當我使用Array(-2, 1, -3, 4, -1, 2, 1, -5, 4)作爲源時，我得到返回(7, 5,8)。但是，正確的答案應該是(6, 3, 6)。下面的代碼。使用動態樣式的MaxSubArray

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 

}

來源

2016-11-08 Duzzz

更多的斯卡拉/功能方法如何？

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)

來源

2016-11-08 10:25:53 Iadams

是不是您的解決方案至少立方？ –

我並沒有試圖對其進行優化，只是爲了直接用功能表達解決方案。事實上@jwvh上面的解決方案是相同的複雜度，我們都生成相同的O（n^2）個子序列並且各自獨立求和。您可以在這裏添加大量優化點，但它有助於從獲得正確答案開始。 – Iadams

獲得正確答案絕對是微不足道的。在O（n）時間獲得正確的答案是這個問題的關鍵。 O（n^2）是您可以考慮進行優化的起點，任何比這更糟糕的東西都可以直接進入/ dev/null。 –

使用動態樣式的MaxSubArray

回答

相關問題