max_sum_subseq.scala

def maxSumSubseq(s: Seq[Int]): Int = {
    (Option.empty[Int] /: s) {
        case (Some(acc), v) if(v < acc+v) => Some(acc+v)
        case (_, v) => Some(v)
    } max
}

def maxSumSubseqIdxs(s: Seq[Int]): ((Int, Int), Int) = {
    val sums = (Option.empty[((Int, Int), Int)] /: s.zipWithIndex) {
        case (Some(((i, _), acc)), (v, j)) if(v < acc+v) =>
            Some(((i,j), acc+v))
        case (_, (v, j)) =>
            Some((j, j) -> v)
    }
    sums.maxBy(_._2)
}