Adjacency List and Prefix Sum (C++)
Intuition\n Describe your first thoughts on how to solve this problem. \nThe Aproach is to use adjacecy list and instead of making a list of connected neighbors
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe Aproach is to use adjacecy list and instead of making a list of connected neighbors, We will store the neighbour\'s value in descending order. After that we will find maximum prefix so that it maximise the output. \n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nvalues - [1,2,3,4,10,-10,-20]\nedges -  [[0,1],[1,2],[1,3],[3,4],[3,5],[3,6]]\nAdjacency List: \n1. Every node is a center node.\n2. store values of connected nodes\n3. sort them in descending order so that we can find at most **K** maximum valued edges.\n4. find prefix sum of each list.\n5. find maximum prefix sum (**>= 0**, because if the maximum prefix sum is negative then we can also take **K = 0**) until we hit atmost **K** valued neighbors (if no of neighbors **>= K** else we will consider all of the neighbors) for a center node.\n6. maximize the output by **max**(*center node value **+** maximum prefix sum value*(can become less than center node value), *center node value*)\n\n\n- [0] -> 2 \n- [1] -> 4 7 8\n- [2] -> 2 \n- [3] -> 10 12 2 -18\n- [4] -> 4\n- [5] -> 4\n- [6] -> 4 \n\nThe maximum prefix sum is **12** (by considering atmost **K** neighbors) for center node **3** which has a value of 4.\nFinal O/P: **12 + 4 = 16**\n# Complexity\n- Time complexity: O(N*ElogE), N = Number of nodes, E = Number of neighbors\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(N + E)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n\n# Code\n```\nclass Solution {\npublic:\n    int maxStarSum(vector<int>& vals, vector<vector<int>>& edges, int k) {\n        int n = vals.size();\n        vector<int> adj[n];\n        for(int i = 0; i<edges.size(); i++) {\n            int s = edges[i][0];\n            int d = edges[i][1];\n            adj[s].push_back(vals[d]);\n            adj[d].push_back(vals[s]);\n        }\n        int maxVal = INT_MIN;\n        for(int i = 0; i<n; i++) {\n            sort(adj[i].begin(), adj[i].end(), greater<int>());\n            for(int j = 1; j<adj[i].size(); j++) {\n                adj[i][j] += adj[i][j-1];\n            }\n            int j = 0;\n            int temp = 0;\n            while(j < min(k, (int)adj[i].size()) ) {\n                temp = max(temp, adj[i][j]);\n                j++;\n            }\n            maxVal = max({maxVal, temp + vals[i], vals[i]});\n        }\n        return maxVal;\n    }\n};\n```
['Prefix Sum', 'C++']