Day4 Leetcode Array系列----Maximum Subarray

本次題目 Maximum Subarray by Ruby

從現存的數字陣列中找出內部加總最多的子陣列

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

思考路線一

1. 可以參考之前寫過的 Container_with_most_water
2. 用pattern matching 指派變數，可能需要紀錄加總結果(sum),紀錄加總最多時的陣列(sub_array),設定前後指針由兩端逼至中間(start_at,end_at)
3. 用 while 迴圈去跑可以設定條件直到子陣列加總最大值出現才結束
4. 比較每次加總結果，紀錄加總最大值時的子陣列

Coding Time

先把基本的東西準備好

given_array = [-2,1,-3,4,-1,2,1,-5,4]

def mxaimum_subarray(arr)
  sum,sub_array,start_at,end_at=[0,[],0,arr.length-1]
end

p mxaimum_subarray(given_array)

準備while迴圈條件就設定當前後兩端碰到時結束，計算與紀錄前後兩端夾出的子陣列加總，當上一次加總值比這次加總值小，就把加總值更換成這次的，此時要記錄子陣列範圍

given_array = [-2,1,-3,4,-1,2,1,-5,4]

def mxaimum_subarray(arr)
  sum,sub_array,start_at,end_at=[0,[],0,arr.length-1]
  while start_at < end_at
    current_sum =arr[start_at..end_at].sum
    
    if sum < current_sum
      sub_array = arr[start_at..end_at]
      sum = current_sum
    end
end

p mxaimum_subarray(given_array)

這個時候要設定什麼狀況下更改前後兩端的位置，不然會陷入無窮迴圈，用比大小的方式，當以start_at為索引取出的值小於以end_at為索引取出的值，我就讓start_at向右移動，如果大於等於就讓end_at向左移動

given_array = [-2,1,-3,4,-1,2,1,-5,4]

def mxaimum_subarray(arr)
  sum,sub_array,start_at,end_at=[0,[],0,arr.length-1]
  while start_at < end_at
    current_sum =arr[start_at..end_at].sum
    
    if sum < current_sum
      sub_array = arr[start_at..end_at]
      sum = current_sum
    end

    if arr[start_at] < arr[end_at]
      start_at += 1
    else
      end_at -= 1
    end

  end
  return sub_array
end

p mxaimum_subarray(given_array)

result [4, -1, 2, 1]

最後，我想增加點檢查，如果使用者傳入的是空陣列，就要反應錯誤訊息，如果傳入的是字串，也要反應錯誤訊息，如果傳入的陣列中參雜文字或不可計算的內容，也要回傳錯誤訊息

# Input: [-2,1,-3,4,-1,2,1,-5,4],
# Output: 6
# Explanation: [4,-1,2,1] has the largest sum = 6.
given_array = [-2,1,-3,4,-1,2,1,-5,4]

def mxaimum_subarray(arr)
  if not arr.is_a?(Array)
    return 'give me array'
  elsif arr.length == 0
    return 'nothing in array'
  else
    arr.each_with_index do |item,idx|
      if item.to_s.match?(/\d/)
        next
      else
        return 'give me number list'
      end
    end
  end

  sum,sub_array,start_at,end_at=[0,[],0,arr.length-1]
  while start_at < end_at
    current_sum =arr[start_at..end_at].sum
    
    if sum < current_sum
      sub_array = arr[start_at..end_at]
      sum = current_sum
    end

    if arr[start_at] < arr[end_at]
      start_at += 1
    else
      end_at -= 1
    end

  end
  puts sum
  return sub_array
end

p mxaimum_subarray(given_array)

result [4, -1, 2, 1]

這裡我用了 is_a? 這個方法檢查傳入的參數是不是陣列

如果傳入的參數是陣列再用 length 判斷是不是空陣列

最後判斷陣列的元素有無參雜文字，這裡我利用字串的match?方法與正規表示法

把陣列中每個元素取出，轉成字串，在比對是不是數字

今天到此為止，有任何問題請在下方留言或透過email、GitHub聯絡我，感謝閱讀

Daily kitty