在Scala中沒有兩個相鄰元素的數組中的最大子序列總和

Question

我想解決計算數組的最大子序列和的問題，而沒有相鄰元素是該總和的一部分。 對於第i個索引處的每個元素，我檢查i-2和i-3元素的最大值，並向其中添加第i個元素以獲得最大值，以便兩個相鄰元素不包含在任何總和中。

我解決它在斯卡拉以下遞歸的方式：ideone link

/** 
* Question: Given an array of positive numbers, find the maximum sum of a subsequence with the constraint that no 2 numbers in the sequence should be adjacent in the array. 
*/ 
object Main extends App { 
    val inputArray = Array(5, 15, 10, 40, 50, 35) 
    print(getMaxAlternativeElementSum(0, 0, inputArray(0))) 
    def getMaxAlternativeElementSum(tracker: Int, prevSum: Int, curSum: Int):Int = tracker match { 
    case _ if tracker == 0 => getMaxAlternativeElementSum(tracker+1, 0, inputArray(tracker)) 
    case _ if tracker >= inputArray.length => curSum  
    case _ => val maxSum = curSum.max(prevSum)    
       getMaxAlternativeElementSum(tracker+1, maxSum, prevSum+inputArray(tracker)) 
    } 
} 

每一次，我是使用遞歸方法執行前兩款項下一次迭代。我可以使用任何Scala成語來優雅地做這個嗎？

Answer 1

不知道如果我理解正確的，你想幹什麼，但也許這會爲你工作：

def getMaxAlternativeElementSum(input: Array[Int]) : Int = { 
    val sums = 
     input.zipWithIndex.fold((0, 0)) { (acc, elem) => 
     elem._2 % 2 match { 
      case 0 => (acc._1 + elem._1, acc._2) 
      case 1 => (acc._1, acc._2 + elem._1) 
     } 
     } 

    if (sums._1 > sums._2) sums._1 else sums._2 
    }