*[topcoder]The Tree

http://community.topcoder.com/stat?c=problem_statement&pm=12786&rd=15733
この問題は面白いです.木の根と各層のノードの個数をあげて、木の直径を求めます.作り方はこの階に二つのノードがあるなら、上と下があり、直径は二を加えます.この階にノードが一つしかないと、この階から下にもう一つしか追加できません.また、この直径は必ずしも根を通るとは限らない.

#include <vector>

using namespace std;



class TheTree {

public:

    int maximumDiameter(vector <int> cnt);

};



int TheTree::maximumDiameter(vector <int> cnt) {

    int D = cnt.size();

    int ans = 0;

    for (int i = 0; i < D; i++) {

        int res = 0;

        int flag = false;

        for (int j = i; j < D; j++) {

            if (cnt[j] == 1)

                flag = true;

            res += (flag ? 1 : 2);

            ans = max(res, ans);

        }

    }

    return ans;

};