[請問] 程式問題請教

[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/ask/M.1709254879.A.E39.html
→ Schottky: 每個 sub array 都至少要有一個負數，所以先把非負數
→ Schottky: 去除，然後想像剩餘負數之間有幾個可以插入分隔線的空位
→ Schottky: 先窮舉出分隔線有幾種插入法。以你舉的例子，分隔線只會
→ Schottky: 有一條而且必須插在-2和-5之間。
→ Schottky: 啊我忘了還可以完全不插 XD
→ Schottky: 下一步再回頭考慮有非負數的狀況，-2和-5之間還有3和4
→ Schottky: 那麼唯一的分隔線有三個位置可以選擇
→ Schottky: 要不要用recursive要不要用dynamic programming都是其次
→ Schottky: 先把演算過程做對比較重要
→ Schottky: 程式類問題可以去相關語言討論板如 C_and_CPP、Python
→ Schottky: 不分語言的討論也可以去Programming
→ Schottky: 這些板看起來冷門，但只要有新文章就會有人去看的
→ thumbg75446: 謝謝我去那邊問問看
推 yzfr6: 陣列