a140. TOI 2020/06 潛力組：蛋糕

題目描述

蛋糕由左到右分成 N 塊，每塊的喜好分數可以是正數、零或負數。你可以取走一段連續的蛋糕，但最多取 K 塊，也可以完全不取。請求出可獲得的最高分數總和。

輸入格式

第一行為 N、K，第二行為 N 個分數 S[i]。 1 ≤ N ≤ 100000；1 ≤ K ≤ N；−100 ≤ S[i] ≤ 100。

輸出格式

輸出最高分數總和；完全不取時分數為 0。

來源

TOI 2020/06/29~2020/07/03 潛力組〈蛋糕〉。本題以自寫文字重述規則，範例與測資另行設計。 https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202006/Cake.pdf