解法自体の解説は解説PDF（https://img.atcoder.jp/abc128/editorial.pdf）を参照してください。
最大値などの代表値を求める問題は、全ての場合の中から該当する場合を見つけることと同じなので、
まず全探索することを考え、必要に応じて貪欲法や動的計画法で不要な場合をカットすることを考えていくとよいと思います。
まず全探索することを考え、必要に応じて貪欲法や動的計画法で不要な場合をカットすることを考えていくとよいと思います。
全探索を行う場合、何らかの規則に基づいて全ての場合を列挙する必要があります。
（例えばfor(int i=0;i<n;i++)文での探索では、indexが小さい順に探索を行っています。）
今回の問題では、左右から取る宝石の個数をそれぞれindexにすることで、全ての場合を列挙できます。
全探索の実装方法を考える際は、何かしらの規則で探索対象を分類できないか考えるとよいと思います。
（例えばfor(int i=0;i<n;i++)文での探索では、indexが小さい順に探索を行っています。）
今回の問題では、左右から取る宝石の個数をそれぞれindexにすることで、全ての場合を列挙できます。
全探索の実装方法を考える際は、何かしらの規則で探索対象を分類できないか考えるとよいと思います。
順に操作を行っていく問題では、可能であれば操作の順番を変えることで、見通しが良くなることがあります。
（逆順に操作をする等）
今回の問題では、宝石を捨てる操作は宝石を取った後ならどのタイミングでもよいので、宝石を取り終わった後に捨てることにします。
これにより、取った宝石を価値が小さいものから貪欲に捨てることができます。
（この部分貪欲法を用いない場合、R=min(n,k)として時間計算量に2^(R+1)がかかってしまうはずです）
（逆順に操作をする等）
今回の問題では、宝石を捨てる操作は宝石を取った後ならどのタイミングでもよいので、宝石を取り終わった後に捨てることにします。
これにより、取った宝石を価値が小さいものから貪欲に捨てることができます。
（この部分貪欲法を用いない場合、R=min(n,k)として時間計算量に2^(R+1)がかかってしまうはずです）
以上の全探索は十分高速に実行することができます。
ちなみに動的計画法でも解くことができます。
（Writer Hyado)
