Ruby解题分享-Maximum Subarray

这题反正就是要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