https://codeforces.com/contest/1668/problem/D
難しい。
公式解説のままです。
まず愚直なDPを考えるdp[i]=i番目まで決めた時のベストスコアとする。 このときAの累積和を求めておけば、j=0からi-1までためして、dp[i]= max(dp[j]+score(j,i)) となる。scoreは区間和の正負で符号が変わる部分列の長さ。
ここで実は部分和を試すのは無駄だとわかる。
なぜなら最適解として長さ2以上の部分和がマイナス部分があったとすると、その部分に含まれる項はすべて負数となるので、長さ1に分割してもスコアは変わらない。（ もし正の数が含まれるなら、全部を長さ1に分割するすることでスコアが良くなって矛盾する）
部分和が0の場合も似たようなことが言える。
よって、（愚直なDPの遷移を考えれば明らかに）DPの更新はスコアが最も良くなる部分からの遷移だけ考えれば良い。
max(score(j,i))は部分和がプラスのうち、max(dp[j]+(i-j)) となる。
k= dp[j]+(i-j)
iが邪魔なので移項して
k-i = dp[j]-j
つまり部分和がプラスのうち(dp[j]-j)の最大値が高速に求まれば良い。
セグ木が使える。
ただし、部分和は大きくなるので、累積和を座標圧縮してセグ木に乗せる必要がある。
解法
累積和をS[i]
dp[i] = i番目まで決めた時のベストスコア
セグ木をseg[sum]=x として 部分和sumがA[i]未満（A[i]-「0からjまでの部分和」がプラスを取得したい）のときのベストスコアを更新に使用する。
ベストスコアがないときは長さ1として追加する。
A[i]未満を候補にするのは、A[i]-sum < 0 つまり部分和がマイナスや0になるなら長さ1とするのが最適だから。
dp[i] = max(dp[i-1]+1 , seg[S[i]] + i )
セグ木の更新
seg[S[i]] = max(seg[S[i]], dp[i] - i )
実際はセグ木は座標圧縮が必要。
以上でAC。
（テストケース毎に出力したらTLEした）
