使用动态样式的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

回答

相关问题