TopCoder SRM 715 Div1 Easy: MaximumRange

するめうめ

tsutaj.hatenablog.com

問題概要

原文 → TopCoder Statistics - Problem Statement

と のみからなる数列が与えられる。 (原文は文字列だけどまあ同じことなので)

この数列の (連続とは限らない) 部分列を取ることを考える。部分列の累積和を取った時の最大と最小の差の最大値を求めよ。

解説

打ち消し合ってしまうので、プラスの要素とマイナスの要素を両方使うことにメリットはありません。よってプラスだけ・もしくはマイナスだけ使うのがよいため、プラスの個数とマイナスの個数のうち大きいほうが答えになります。

ソースコード

class MaximumRange {
    public:
    int findMax(string s) {
        int a = 0, b = 0;
        for(auto x : s) {
            (x == '+' ? a : b)++;
        }
        return max(a, b);
    }
};

ABC の B 問題でありそう。少なくとも Div1 Easy ではない・・・。