天府城有一排土地由左到右編號 1∼N,每塊土地有他蓋一棟建築帶來的價值。你想要在這裏投資一些土地並建起一些房屋,然而由於連續的房屋失火時容易蔓延,你希望投資的所有房屋不會恰形成一段完整的連續區間(也就是說,不存在 l,r 使得對於所有房屋 x,x 被你投資若且唯若 l≤x≤r),並且你不能全部不投資房屋。你的投資總收益是你在所有蓋房屋的土地上收益總和。請你回答在滿足條件下的最大收益。
本題包含多筆測資,輸入第一行是一個整數 T,代表測資筆數。
每筆測資輸入兩行,第一行是一個整數 N,代表土地數量。 第二行有 N 個空白分隔的整數 ai(1≤i≤N),代表投資第 i 塊土地價值。
輸入保證 T≤105,3≤N≤3×105,−1000≤ai≤1000,且單筆輸入所有 N 總和不超過 3×105。
對於每筆測資輸出一行一個整數,代表最大投資收益。
NPSC