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

[thumbg75446 (EDWIN)]

請教一個問題，給定一個整型數組，值有正有負，需要把整個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
推 gusion: 這個問題的分割方式，簡化來看，就是在兩
→ gusion: 個負數之間的逗號位置選一個切一刀，或者
→ gusion: 不選，所以範例中的-2和-5之間有三個逗號
→ gusion: 位置可以分割，也可以不選，因此共(3+1)種
→ gusion: 計算逗號數的方式就兩個index相減就好
→ gusion: 如果array中有很多負數也是同理，只要把兩
→ gusion: 個負數間可以切的方式數量乘起來就好
→ gusion: 例如：1, -2, 3, 4, -5, -6, 7, -8, 9
→ gusion: 共 (3+1)*(1+1)*(2+1) 種分割方式
→ gusion: 寫成code就是直接array掃一遍，掃到負數時
→ gusion: ，看跟前一個負數差多少index，加一後乘在
→ gusion: result變數應該就可
→ thumbg75446: 謝謝回答 但是是否遇到連續負數的arr
→ thumbg75446: ay就沒辦法了呢？比如說[-1,-1,-1,-1
→ thumbg75446: ,3]
推 gusion: 連續負數也可以啊，上面推文例子的-5和-6
→ gusion: 就是，兩個index差1，中間可以切一刀，或
→ gusion: 者不切，所以就是(1+1)，然後跟其他段的數
→ gusion: 量乘起來就好
→ gusion: 你的例子就是(1+1)*(1+1)*(1+1)，共8種
→ thumbg75446: 謝謝回覆 理解了