→ neverfly:第三個step，O(n)做的完嗎？ 05/19 14:43
→ aknow:2n=O(n) 05/19 14:44
上面的都對
不過在這問題裡有個很重要的地方
那就是
不看正負號的話, 整數都是越乘越大!!!
所以大略是
只要簡單找一段偶數個負號
然後讓這段越長就越好
不考慮一些boundary condition
只提大概
方法如下
看到0就切斷 O(n)
所以現在有一段段沒有0的
對於一段找最大的方法
1. 長度為1, 就是這個
2. 頭到尾數一次
如果有偶數個負號
那這整個就是最大的
3. 若是奇數個負號
左邊少幾個讓他變成偶數個
或是右邊少幾個
選一個乘起來最大的
O(n)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.166.200.179
※ 編輯: aknow 來自: 218.166.200.179 (05/19 10:10)