這題反正就是要more and more...

Maximum Subarray

題目連結:https://leetcode.com/problems/maximum-subarray/
題目重點:求陣列中,連續幾個值的和中最大的和值,不是求那組數列。

[-2, 1, -3, 4, -1, 2, 1, -5, 4]
回傳6 , 不是回傳[4, -1, 2, 1]

整理

def max_sub_array(nums)

end

p max_sub_array([-2,1,-3,4,-1,2,1,-5,4]) #=> 6
p max_sub_array([1]) #=> 1
p max_sub_array([5,4,-1,7,8]) #=> 23

先離開題目,我們改看另一些陣列。

#無論用哪種邏輯解,我們都是在找連續數字中,加起來最大的,所以我們需要一個變數來記錄序列和,只留下最大的。
#max_sum = 0

[1]
#最大和是 1, 1 = 1 + 0 或 1 = 0 + 1

[-1, 1] 
[-1 ,-2, 3]
#陣列中如果有負數和在前面,那最大和一定會是從正數開始。

[1, -1 ,-2, 3] #最大和3 ,還是自己, x是第一個數字, x + -1 + -2 < 0
[2, -1 ,-2, 3] #最大和3 ,還是自己
[3, -1 ,-2, 3] #最大和3 ,是3 + -1 + -2 + 3 也是3自己, x + -1 + -2 = 0
[4, -1 ,-2, 3] #最大和4 ,是Array.sum,也是4自己, x + -1 + -2 > 0了。
#所以前面的序列和要大於0時,才會有意義,那序列和是負數時,都當0來看,相對的大於0時的序列和,繼續跟當前數字相加才有可能超過最大和。

[5, -6, 6] #陣列中如果有負號在中間。
#0 + 5 ,和 = 5, 最大和5
#5 + -6 = -1,最大和還是5
#5 + -6 + 6 , 由上面看, 前面和是負數的序列我們不要, 所以變成 0 + 6, 最大和變6。

以上好像叫貪心邏輯??

接著看我們第一個例子

[-2, 1, -3, 4, -1, 2, 1, -5, 4] #第一個數字負數不要,或是想成"負數和變成0",也可想成負數捨棄掉。
# 我們還是從頭看
#array[0], 0 + -2 = -2, 最大和-2, 要給下一個數字相加的數值是負數, 自動變0。
#array[1], 0 + 1 = 1, 最大和1, 要給下一個數字相加的數值是正數, 持續為1。
#array[2], 1 + -3 = -2,最大和還是1, 給下一個數字要給下一個數字相加的數值是負數, 自動變0。
#array[3], 0 + 4 = 4,最大和4 ,要給下一個數字相加的數值是正數, 持續為4。
#array[4], 4 + -1 = 3,最大和還是4,要給下一個數字相加的數值是正數, 持續為3。
#array[5], 3 + 2 = 5 ,最大和變5,給下一個相加數字5。
#array[6], 5 + 1 = 6 ,最大和變6,給下一個相加數字6。
#array[7], 6 + -5 = 1, 最大和還是6,給下一個相加數字變1。
#array[8], 1 + 4 = 5。最大和還是6。

#整理一下,看看我們需要幾個變數。
max_sum = 0 #最大和
for_next_add = 0 #給下一個數字相加數值,由0開始。
max_sum = for_next_add = 0 #可以寫一起

[-1, 1] 
#陣列前面數字負數時。
#最大和與相加數的關係,在-1時。
for_next_add = [0 + -1].max
max_sum = [ 0, -1].max

for_next_add = [ num , num + for_next_add].max
max_sum = [for_next_add, max_sum].max

答案

#老話一句,學Ruby多用each與map。
def max_sub_array(nums)
  max_sum = for_next_add = 0
  nums.each_with_index do |num, index|
    for_next_add = [ num , num + for_next_add].max
    max_sum = [for_next_add, max_sum].max
  end
  max_sum
end

順帶一提,我忘了我前面有沒有分享過,變數先指向0,就會成為一個物件,程式碼再動,物件也會隨程式碼改變值,雖然無法解釋物件導向,但可以感受一下,物件導向的感覺。

解題心法,沒解過的題目都很難,解過的題目好像都很簡單?

上面答案於leetcode少判斷如果num.size == 1時的狀況,稍微修改一下內容。

def max_sub_array(nums)
  max_sum = for_next_add = nums.shift
  nums.each_with_index do |num, index|
    for_next_add = [ num , num + for_next_add].max
    max_sum = [for_next_add, max_sum].max
  end
  max_sum
end