# Maximum Sum of Edge Values in a Graph
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximum-sum-of-edge-values-in-a-graph)
Canonical: https://scaleengineer.com/dsa/problems/maximum-sum-of-edge-values-in-a-graph
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting), [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Graph
---
## Problem
You are given an **undirected connected** graph of `n` nodes, numbered from `0` to `n - 1`. Each node is connected to **at most** 2 other nodes.

The graph consists of `m` edges, represented by a 2D array `edges`, where `edges[i] = [ai, bi]` indicates that there is an edge between nodes `ai` and `bi`.

You have to assign a **unique** value from `1` to `n` to each node. The value of an edge will be the **product** of the values assigned to the two nodes it connects.

Your score is the sum of the values of all edges in the graph.

Return the **maximum** score you can achieve.

**Example 1:**

![](https://assets.glich.co/dsa/maximum-sum-of-edge-values-in-a-graph/image0.png) 

**Input:** n = 4, edges = \[\[0,1\],\[1,2\],\[2,3\]\]

**Output:** 23

**Explanation:**

The diagram above illustrates an optimal assignment of values to nodes. The sum of the values of the edges is: `(1 * 3) + (3 * 4) + (4 * 2) = 23`.

**Example 2:**

![](https://assets.glich.co/dsa/maximum-sum-of-edge-values-in-a-graph/image1.png) 

**Input:** n = 6, edges = \[\[0,3\],\[4,5\],\[2,0\],\[1,3\],\[2,4\],\[1,5\]\]

**Output:** 82

**Explanation:**

The diagram above illustrates an optimal assignment of values to nodes. The sum of the values of the edges is: `(1 * 2) + (2 * 4) + (4 * 6) + (6 * 5) + (5 * 3) + (3 * 1) = 82`.

**Constraints:**

* `1 <= n <= 5 * 104`
* `m == edges.length`
* `1 <= m <= n`
* `edges[i].length == 2`
* `0 <= ai, bi < n`
* `ai != bi`
* There are no repeated edges.
* The graph is connected.
* Each node is connected to at most 2 other nodes.

# Approaches
## Brute Force with Permutations
The most straightforward but naive approach is to try every possible assignment of values to nodes. Since we need to assign a unique value from `1` to `n` to each of the `n` nodes, the problem is equivalent to finding the best permutation of these values. We can generate all `n!` permutations of the numbers `1` through `n`. For each permutation, we can assign the values to the nodes (e.g., assign the `i`-th value in the permutation to node `i`) and calculate the resulting sum of edge values. By comparing the scores from all permutations, we can find the maximum possible score.
**Time:** O(n! * m), where `n` is the number of nodes and `m` is the number of edges. Generating `n!` permutations takes O(n * n!) time, and for each, we iterate through `m` edges to calculate the score. Given `m <= n`, this is at least O(n * n!). · **Space:** O(n) for the recursion stack depth and the arrays used to store the current permutation and used values.
**Pros:** Guaranteed to find the optimal solution.; Conceptually simple and easy to understand.
**Cons:** Extremely inefficient due to its factorial time complexity.; Only feasible for very small values of `n` (e.g., `n <= 10`).; Fails to pass the time limits for the given constraints.
### Explanation
This method explores the entire solution space exhaustively. The core of the algorithm is a function that can generate all permutations of a set of numbers. A common way to implement this is using a recursive backtracking algorithm.

Here's a conceptual outline of the code:

```java
class Solution {
    long maxScore = 0;

    public long maximumScore(int n, int[][] edges) {
        List<Integer> values = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            values.add(i);
        }

        // Adjacency list for the graph
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
        }

        // Generate all permutations and calculate score for each
        permute(new int[n], new boolean[n + 1], 0, n, edges);

        return maxScore;
    }

    private void permute(int[] assignment, boolean[] used, int k, int n, int[][] edges) {
        if (k == n) {
            // A full assignment is created, calculate its score
            long currentScore = 0;
            for (int[] edge : edges) {
                currentScore += (long) assignment[edge[0]] * assignment[edge[1]];
            }
            maxScore = Math.max(maxScore, currentScore);
            return;
        }

        for (int val = 1; val <= n; val++) {
            if (!used[val]) {
                assignment[k] = val;
                used[val] = true;
                permute(assignment, used, k + 1, n, edges);
                used[val] = false; // backtrack
            }
        }
    }
}
```
This code generates permutations of values and assigns them to nodes `0` to `n-1` in order. For each complete permutation, it calculates the score and updates the maximum.
### Algorithm
1. Generate all `n!` permutations of the values `{1, 2, ..., n}`.
2. For each permutation, treat it as an assignment of values to nodes `0, 1, ..., n-1`.
3. For a given assignment (permutation), calculate the total score by summing the products of values for all connected nodes (edges).
4. Keep track of the maximum score found across all permutations.
5. Return the overall maximum score.

## Dynamic Programming on Subsets
A significant improvement over brute force can be achieved using dynamic programming, particularly a technique known as DP on subsets or DP with bitmasking. This is often used for problems like the Traveling Salesperson Problem (TSP), which involve finding an optimal ordering. Since our graph is a simple path or cycle, we can unroll it into a sequence of nodes and try to build the optimal value assignment incrementally.

The idea is to build the assignment one node at a time. A DP state could store the maximum score for a partially completed assignment. For example, `dp[mask][i]` could be the maximum score achieved by assigning values to a subset of nodes (represented by `mask`), where the last node in the sequence was `i`.
**Time:** O(n^2 * 2^n), which is exponential. · **Space:** O(n * 2^n) or O(n^2 * 2^n) depending on the state definition.
**Pros:** Much more efficient than the factorial complexity of the brute-force approach.; Can solve the problem for moderately sized `n` (e.g., `n <= 20`).
**Cons:** The time and space complexity are exponential, making it infeasible for the given constraints (`n` up to 50,000).; The DP state and transitions are complex to define and implement correctly for this specific problem.
### Explanation
Let's try to formulate a DP. First, we find the node sequence of the path or cycle, `p_0, p_1, ..., p_{n-1}`. A possible DP state could be `dp[i][mask]`, representing the maximum score for an assignment on the first `i` nodes of the path (`p_0` to `p_{i-1}`), using the set of values represented by the bitmask `mask`.

To compute `dp[i][mask]`, we would need to know which value was assigned to node `p_{i-1}` to calculate the edge product `v(p_{i-2}) * v(p_{i-1})`. This suggests the value assigned to the last node must be part of the state.

Let's define `dp[i][v][mask]` as the maximum score for the subproblem on the first `i` nodes (`p_0, ..., p_{i-1}`), where the values used are represented by `mask`, and node `p_{i-1}` is assigned value `v`.

`dp[i][v][mask] = max_{u in mask, u != v} (dp[i-1][u][mask \setminus \{v\}] + u * v)`

- `i`: index of the node in the path sequence (from 1 to `n`).
- `v`: value assigned to node `p_{i-1}` (from 1 to `n`).
- `mask`: a bitmask representing the set of values used so far.

The state space is `O(n * n * 2^n)`, which is too large. Even with optimizations, this approach remains exponential and cannot solve the problem for the given constraints.
### Algorithm
1. Recognize that the graph structure (path or cycle) allows for a dynamic programming approach, similar to the Traveling Salesperson Problem (TSP).
2. Determine the sequence of nodes along the path or cycle, let's say `p_0, p_1, ..., p_{n-1}`.
3. Define a DP state `dp[mask][i][v]` representing the maximum score for assigning values from a subset `S` (represented by bitmask `mask`) to the first `|S|` nodes of the path, ending with node `p_{i-1}` being assigned value `v`.
4. The transitions would involve trying to extend the path by one node and one value, calculating the new score.
5. The state space would be `n * n * 2^n`, which is too large. A more standard TSP-like DP state would be `dp[mask][i]`, the max score for a path of nodes in `mask` ending at node `i`, using values `{1, ..., popcount(mask)}`. This is still complex to formulate correctly and is exponential.

## Greedy Algorithm based on Graph Structure
The key to an efficient solution lies in analyzing the graph's structure and finding a greedy strategy for value assignment. The constraint that each node has a degree of at most 2 means the connected graph must be either a simple path or a simple cycle. This drastically simplifies the problem.

The goal is to maximize the sum of products `v_i * v_j`. Intuitively, we want to multiply large numbers with other large numbers. This suggests a specific arrangement of values along the path or cycle.

- **For a cycle:** The optimal arrangement is an 'alternating' or 'up-down' permutation of values. For `{1, ..., n}`, this sequence is formed by taking odd numbers in increasing order, then even numbers in decreasing order (e.g., `1, 3, 5, ..., 6, 4, 2`).
- **For a path:** Nodes with degree 2 are 'more important' as their value contributes to two products. Thus, they should be assigned the largest `n-2` values (`{3, ..., n}`). The two endpoints (degree 1) get the smallest values (`{1, 2}`). The arrangement of the inner `n-2` values also follows an alternating pattern to maximize their internal sum of products. The endpoint values `1` and `2` are then attached to the ends of this sequence in a way that maximizes the sum.
**Time:** O(n) because each step (building graph, finding structure, traversing, generating sequences, and calculating the final sum) takes time proportional to the number of nodes `n` (since `m <= n`). · **Space:** O(n) to store the adjacency list, degrees, node sequence, and value sequence.
**Pros:** Highly efficient with linear time and space complexity.; Provides the optimal solution for the given constraints.; Leverages the specific structure of the graph for a simple and fast algorithm.
**Cons:** The logic for the optimal arrangement of values is not immediately obvious and relies on insights into permutation optimization problems.; The implementation requires careful handling of the path and cycle cases separately.
### Explanation
This approach is linear in time and space, making it highly efficient.

**Algorithm Steps:**

1.  **Graph Representation:** Build an adjacency list and a `degree` array from the `edges` input.
2.  **Structure Identification:** Find a node with degree 1. If one exists, it's a path; start the traversal from there. Otherwise, it's a cycle; start from node 0.
3.  **Node Traversal:** Create an ordered list of nodes (`nodeSequence`) by traversing the path/cycle.
4.  **Value Assignment Strategy:**
    - **If Cycle:** Generate the alternating value sequence for `{1, ..., n}`. The total score is the sum of products of adjacent elements in this sequence, including the connection between the last and first elements.
    - **If Path:** 
        a. Generate the alternating value sequence (`innerValues`) for the numbers `{3, ..., n}`.
        b. Let the first and last elements of `innerValues` be `p_first` and `p_last`. To maximize `1*p_x + 2*p_y`, we should pair the larger of `{1,2}` with the larger of `{p_first, p_last}`. However, the problem is to decide which end of the path gets which value. The optimal choice is to pair the smaller endpoint value (1) with the end of the inner sequence that has the smaller value, and the larger endpoint value (2) with the end that has the larger value. Let's say `p_first < p_last`. The final value sequence will be `1`, followed by `innerValues`, then `2`. 
        c. Calculate the sum of products for this final sequence.

**Code Snippet:**
```java
import java.util.*;

class Solution {
    public long maximumScore(int n, int[][] edges) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        int[] degree = new int[n];

        for (int[] edge : edges) {
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
            degree[edge[0]]++;
            degree[edge[1]]++;
        }

        boolean isCycle = true;
        int startNode = 0;
        for (int i = 0; i < n; i++) {
            if (degree[i] == 1) {
                isCycle = false;
                startNode = i;
                break;
            }
        }

        List<Long> valueSequence;
        if (isCycle) {
            valueSequence = generateAlternatingSequence(1, n);
        } else {
            List<Long> innerValues = generateAlternatingSequence(3, n);
            long firstInner = innerValues.get(0);
            long lastInner = innerValues.get(innerValues.size() - 1);
            
            valueSequence = new ArrayList<>();
            if (firstInner < lastInner) {
                valueSequence.add(1L);
                valueSequence.addAll(innerValues);
                valueSequence.add(2L);
            } else {
                valueSequence.add(2L);
                valueSequence.addAll(innerValues);
                valueSequence.add(1L);
            }
        }

        long totalScore = 0;
        for (int i = 0; i < n - 1; i++) {
            totalScore += valueSequence.get(i) * valueSequence.get(i + 1);
        }
        if (isCycle) {
            totalScore += valueSequence.get(n - 1) * valueSequence.get(0);
        }

        return totalScore;
    }

    private List<Long> generateAlternatingSequence(long start, long end) {
        if (start > end) return new ArrayList<>();
        List<Long> smallHalf = new ArrayList<>();
        List<Long> largeHalf = new ArrayList<>();
        for (long i = start; i <= end; i++) {
            if ((i - start + 1) % 2 != 0) {
                smallHalf.add(i);
            } else {
                largeHalf.add(i);
            }
        }
        Collections.reverse(largeHalf);
        List<Long> result = new ArrayList<>(smallHalf);
        result.addAll(largeHalf);
        return result;
    }
}
```
### Algorithm
1. **Build Graph and Find Degrees:** Construct an adjacency list and an array to store the degree of each node. This takes O(n + m) time.
2. **Identify Graph Structure:** Check the degrees. If there are two nodes with degree 1, the graph is a path. If all nodes have degree 2, it's a cycle. This takes O(n).
3. **Determine Node Sequence:** Perform a traversal (like DFS) starting from an endpoint (for a path) or any node (for a cycle) to get the ordered sequence of nodes. This takes O(n).
4. **Generate Optimal Value Sequence:**
   - **For a cycle:** The values to assign are `{1, 2, ..., n}`. Generate an alternating sequence by taking all odd numbers in increasing order, followed by all even numbers in decreasing order (e.g., for n=6: `1, 3, 5, 6, 4, 2`).
   - **For a path:** The `n-2` inner nodes (degree 2) get values from `{3, ..., n}`, and the 2 endpoints (degree 1) get `{1, 2}`. First, generate the alternating sequence `P` for the inner values `{3, ..., n}`. Then, assign `1` and `2` to the endpoints based on the first and last values of `P` to maximize the terminal products.
5. **Calculate Score:** With the ordered node sequence and the optimal value sequence, map values to nodes and compute the total sum of edge products. This takes O(n).