就在挑選好最大的杯子後,野獸先輩正要端上一杯杯的昏睡紅茶給顧客享用,然而先輩手一滑讓杯子掉到地上碎掉了,在悲痛欲絕的同時,他僥倖希望仍有一些紅茶留下來,趴下身子發現碎掉的玻璃有著高低分布,其中低窪處留下了紅茶。
先輩發現碎掉的玻璃共構成長度為$n$而高度不一的形狀,先輩想要知道最多有多少紅茶剩下來,所以需要你的幫忙去找出低窪處最多能裝多少紅茶。舉例,有長度為6的一串玻璃,其中高度分別為[4,2,0,3,2,5],根據下圖可以發現能裝的紅茶大小為9,也就是最多的紅茶。
輸入的第一行有一正整數$T$,代表接下來有$T$行的測資
每一行(測資)第一個整數為$k$,代表該測資玻璃長度,接下來有$k$個整數$a_i$代表玻璃碎片高度
輸出每筆測資中所剩最大紅茶數量,每筆測資佔一行
2 12 0 1 0 2 1 0 1 3 2 1 2 1 6 4 2 0 3 2 5
6 9
$1\leq T\leq 10$
$2\leq k\leq 2\times 10^4$
$0\leq a_i\leq 10^5$
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |