まあ。思考を書いてみる。
（たたき台、プログラムは任せた）
a)
数列すべて負なら、最大値を見つける O(n)

b-1)
数列にプラスの連続、マイナスの連続があるなら、符号ごとでまとめてしまう O(n)
-1, 3,-,4 2, 3, 5, -6, 10, 1, -100
↓
-1, 3, -4, 8, -6, 11, -100

b-2)
最初と最後が負なら、カウントしない。
うまくく言葉にできんが、順番に足していって、負になったらそれより前と後ろは別に計算する。
多分O(n)以下でできる。

b-3)
出来上がったら、O(n^2)のアルゴリズムで検証する