实用的 each_cons 方法,Ruby 30 天刷题修行篇第十二话

嗨,我是A Fei,今天真的忙翻,以下是今天的题目:
(题目来源: Codewars


The maximum sum subarray problem consists in finding the maximum sum of a contiguous subsequence in an array or list of integers:

maxSequence [-2, 1, -3, 4, -1, 2, 1, -5, 4]
-- should be 6: [4, -1, 2, 1]

Easy case is when the list is made up of only positive numbers and the maximum sum is the sum of the whole array. If the list is made up of only negative numbers, return 0 instead.

Empty list is considered to have zero greatest sum. Note that the empty list or array is also a valid sublist/subarray.


题目要我们在某长度不固定的阵列中,取得「连续数字」相加的最大值,如果是空阵列或负数,则回传 0。这题难点在於,这「连续数字」是不固定的,有可能是两个一组,或三个一组。

以下是我的解答:

def max_sequence(arr)
  array = []
  i = 1
  return 0 if arr.length == 0
  while i <= arr.length 
    array << arr.each_cons(i).reduce{|a, b| a.sum > b.sum ? a : b }.sum 
    i += 1
  end
  array.max.positive? ? array.max : 0 
end

使用前几天学到的 each_cons 方法,迭代出一个一组的元素,再用 reduce 互相比较,将最大值塞进 array 中,接着进行下一轮回圈,两个一组、三个一组...直到连续数字最多的一组(也就是等於阵列长度),我们便可以得到各分组最大的值,并且把它们存进 array 中。

对比最高评分的解答:

def max_sequence(array)
  (1..array.size).map { |i| array.each_cons(i).map(&:sum) }.flatten.push(0).max
end

它使用了(1..array.size),达到 while 回圈的效果。这里一样使用 each_cons,将各分组(n 个连续数字)迭代的每一个阵列,用 sum 算出总合,接着会得到一个二维阵列,可以用 flatten 把它摊平,最後用 max 找出最大值。为了避免空阵列和负数,它巧妙地在 flatten 後 push 一个 0 进去,让结果符合题意。


<<:  {DAY 15} Pandas 学习笔记 part.1

>>:  【Day 14】深度学习(Deep Learning)

没有登入也可以看得到内容? Mendix上的Anonymous User

如果应用程序主要是用於行销的功能,我们常会碰到许多Anonymous User造访,为了防止资料外泄...

[Day17]程序菜鸟自学C++资料结构演算法 – 堆积实作与应用

前言:昨天讲解完了堆积的概念,今天要来实际操作一遍,在查找资料之余,有发现一个有趣的ACM程序竞赛题...

认识 Laravel Queue Jobs

什麽是 Queue Jobs? 学过资料结构的朋友一定不陌生,queue 是一种先进先出的资料结构。...

[Day11] 注册API – urls之专案资料夹

夥伴们大家好,时间过得好快,不知不觉已经到了铁人赛的第十一天,那麽今天来到我们的urls.py,这里...