Clean CPP Intuitive Code
Intuition\nDivide the problem as much as possible into small units and make a function for each unit.\n\n# Approach\nDP with storage of max 3 and min 2 elements
# Intuition\nDivide the problem as much as possible into small units and make a function for each unit.\n\n# Approach\nDP with storage of max 3 and min 2 elements.\n\n# Complexity\n- Time complexity:\nO(n)\n\n- Space complexity:\nO(n^2)\n\n# Code\n```\ntypedef long long ll;\ntypedef vector<int> VI;\ntypedef vector<VI> VVI;\ntypedef vector<ll> VL;\n\nclass Solution {\npublic:\n    ll calc(VL &v1, VL &v2){\n        //its not necessary that we have 3, 2 elements respectively\n        //but m1 will have more than m2 elements for sure\n        int n1 = v1.size(), n2 = v2.size();\n        if(n1 == 1 || n1 == 2){\n            return 1;\n        }\n        //n1 >= 3\n        ll val = v1[0] * v1[1] * v1[2];\n        if(n2 == 1){\n            //this could be negative or positive\n            if(v2[0] < 0){\n                //if v1[2] is negative and v1[0] and v1[1] are positive then we can benefit\n                //if both v1[1] and v1[2] are negative and v1[0] is positive\n                val = max(val, v1[0] * v1[2] * v2[0]);\n            }\n        }\n        else if(n2 == 2){\n            if(v2[0] < 0 && v2[1] < 0){\n                val = max(val, v2[0] * v2[1] * v1[0]);\n            }\n        }\n        return val;\n    }\n    void merge(VL &m1, VL &m2, VL m1t, VL m2t){\n        //we want to maintain max three and min two\n        //m1 = {maximum, second maximum, third maximum}\n        //m2 = {minimum, second minimum}\n        VL v3;\n        for(auto x: m1) v3.push_back(x);\n        for(auto x: m2) v3.push_back(x);\n        for(auto x: m1t) v3.push_back(x);\n        for(auto x: m2t) v3.push_back(x);\n\n        sort(v3.begin(), v3.end(), greater<int> ()); \n        m1.clear(), m2.clear();\n        \n        int n = v3.size();\n        for(int i=0;i<min(n, 3);i++) m1.push_back(v3[i]);\n        for(int i=n-1;i >= max(3, n-2);i--){\n            m2.push_back(v3[i]);\n        }\n    }\n    pair<VL, VL> dfs(int i, int parent, VVI &graph, VI &cost, VL &ans){\n        VL m1, m2;\n        m1.push_back(cost[i]);\n        for(auto child: graph[i]){\n            if(child == parent) continue;\n            pair<VL, VL> temp = dfs(child, i, graph, cost, ans);\n            merge(m1, m2, temp.first, temp.second);\n        }\n        ans[i] = calc(m1, m2);\n        ans[i] = max(ans[i], 0ll);\n        return {m1, m2};\n    }\n    vector<long long> placedCoins(vector<vector<int>>& edges, vector<int>& cost) {\n        //all neg -> product of max 3 negatives\n        //one pos, all neg -> pos * min_two_negatives\n        //two pos, all neg -> if more than two neg, then make the max product with the two min negatives and take max of pos\n        //two pos, one neg -> no option\n        //three pos, all neg -> max(min_two_negative * max_pos, three max positives)\n        int n = cost.size();\n        VVI graph(n);\n        for(auto x: edges){\n            graph[x[0]].push_back(x[1]);\n            graph[x[1]].push_back(x[0]);\n        }\n        vector<ll> ans(n);\n        dfs(0, -1, graph, cost, ans);\n        return ans;\n    }\n};\n```
['C++']