iT邦幫忙

2021 iThome 鐵人賽

DAY 12
0
自我挑戰組

從真「新」鎮出發!30天的刷題修行篇,讓寫程式成為新必殺技系列 第 12

實用的 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 進去,讓結果符合題意。


上一篇
輕鬆排序!sort 的延伸用法,Ruby 30 天刷題修行篇第十一話
下一篇
浮點數和整數的計算,Ruby 30 天刷題修行篇第十三話
系列文
從真「新」鎮出發!30天的刷題修行篇,讓寫程式成為新必殺技16

尚未有邦友留言

立即登入留言