PTT數位生活區 / Programming

[問題] 分割陣列問題請教

看板Programming作者 (EDWIN)時間9月前 (2024/03/01 13:20), 編輯推噓2(2推 0噓 19→)
留言21則, 2人參與, 9月前最新討論串1/1
請教一個問題，給定一個整型數組，值有正有負，需要把整個arr分割成若干個subarr， 但必須滿足每個subarr都至少包含一個負數，請問有幾種分割數？ 例如[1,-2,3,4,-5]只有以下分割方式 [1,-2 | 3,4,-5] [1,-2,3 | 4,-5] [1,-2,3,4 | -5] [1,-2,3,4,-5] 不分割 想問一下具體的思路是什麼？有人說是dp+recursive但我看不太出來.. 謝謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.70.171.68 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Programming/M.1709270459.A.7DA.html
推
03/01 14:07, 9月前 , 1F
這個問題的分割方式，簡化來看，就是在兩
03/01 14:07, 1F
→
03/01 14:07, 9月前 , 2F
個負數之間的逗號位置選一個切一刀，或者
03/01 14:07, 2F
→
03/01 14:07, 9月前 , 3F
不選，所以範例中的-2和-5之間有三個逗號
03/01 14:07, 3F
→
03/01 14:07, 9月前 , 4F
位置可以分割，也可以不選，因此共(3+1)種
03/01 14:07, 4F
→
03/01 14:07, 9月前 , 5F
計算逗號數的方式就兩個index相減就好
03/01 14:07, 5F
→
03/01 14:07, 9月前 , 6F
如果array中有很多負數也是同理，只要把兩
03/01 14:07, 6F
→
03/01 14:07, 9月前 , 7F
個負數間可以切的方式數量乘起來就好
03/01 14:07, 7F
→
03/01 14:07, 9月前 , 8F
例如：1, -2, 3, 4, -5, -6, 7, -8, 9
03/01 14:07, 8F
→
03/01 14:07, 9月前 , 9F
共 (3+1)*(1+1)*(2+1) 種分割方式
03/01 14:07, 9F
→
03/01 14:07, 9月前 , 10F
寫成code就是直接array掃一遍，掃到負數時
03/01 14:07, 10F
→
03/01 14:07, 9月前 , 11F
，看跟前一個負數差多少index，加一後乘在
03/01 14:07, 11F
→
03/01 14:07, 9月前 , 12F
result變數應該就可
03/01 14:07, 12F
→
03/01 14:23, 9月前 , 13F
謝謝回答 但是是否遇到連續負數的arr
03/01 14:23, 13F
→
03/01 14:23, 9月前 , 14F
ay就沒辦法了呢？比如說[-1,-1,-1,-1
03/01 14:23, 14F
→
03/01 14:23, 9月前 , 15F
,3]
03/01 14:23, 15F
推
03/01 14:48, 9月前 , 16F
連續負數也可以啊，上面推文例子的-5和-6
03/01 14:48, 16F
→
03/01 14:48, 9月前 , 17F
就是，兩個index差1，中間可以切一刀，或
03/01 14:48, 17F
→
03/01 14:48, 9月前 , 18F
者不切，所以就是(1+1)，然後跟其他段的數
03/01 14:48, 18F
→
03/01 14:48, 9月前 , 19F
量乘起來就好
03/01 14:48, 19F
→
03/01 14:50, 9月前 , 20F
你的例子就是(1+1)*(1+1)*(1+1)，共8種
03/01 14:50, 20F
→
03/01 17:42, 9月前 , 21F
謝謝回覆 理解了
03/01 17:42, 21F
‣ 更多 thumbg75446 的文章
文章代碼(AID): #1buMMxVQ (Programming)
Programming 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 thumbg75446 的文章
文章代碼(AID): #1buMMxVQ (Programming)