番号が小さいほうから順にステージをクリアしていくことを考えます。

\(\operatorname{dp}[i]\coloneqq{}\)ステージ \(1,\) ステージ \(2,\ldots,\) ステージ \(i\) のうち、ステージ \(i\) を含む \(1\) ステージ以上を選んでクリアした時点で獲得できるスコアの最大値 \((1\le i\le N)\) とします。 便宜上 \(\operatorname{dp}[0]=0\) とします。 求める答えは \(\displaystyle\max _ {0\le j\le N}\operatorname{dp}[j]\) です。

次のような漸化式で \(\operatorname{dp}[i]\) を求めることができます（直前にクリアしたステージが何番目のステージかで場合分けを行っていると考えられます）。

\[\operatorname{dp}[i]=\max\lbrace A _ i+C+\operatorname{dp}[i-1],A _ i+\max _ {0\le j\lt i-1}\operatorname{dp}[j]\rbrace\]

ここで \(\displaystyle\max _ {0\le j\lt i-1}\operatorname{dp}[j]\) を毎回 \(\Theta(i)\) 時間かけて求めると全体で \(\Theta(N ^ 2)\) 時間となってしまいますが、先頭からの累積 \(\max\) として改めて管理することで \(O(N)\) 時間とすることができます。

実装例は以下のようになります。

#include <iostream>
using namespace std;

int main() {
    int N, C;
    cin >> N >> C;

    long ans = 0, prev = -1000000000;
    for (int i = 0; i < N; ++i) {
        int A;
        cin >> A;
        prev = max(ans + A, prev + A + C);
        ans = max(ans, prev);
    }
    cout << ans << endl;
    return 0;
}

N, C = map(int, input().split())

ans = 0
prev = -1000000000
for A in map(int, input().split()):
    prev = max(ans + A, prev + A + C)
    ans = max(ans, prev)

print(ans)