There are $$$n$$$ points on the $$$x$$$-axis whose positions are known to you. Each point has a value $$$a_i$$$ (positive, negative or zero). There is an edge between $$$i$$$ and $$$j$$$ if $$$abs(x_i-x_j) \lt D$$$, where $$$D$$$ is given to you. You must pick some subset $$$S$$$ (possibly empty) of these points such that

• for a given $$$k$$$, there are at most $$$k$$$ connected components in the subgraph induced by the points in $$$S$$$.
• $$$\sum\limits_{i \in S} a_i$$$ is maximized.

What is the maximum possible answer assuming $$$k = \infty$$$?

$$$\sum\limits_{a_i \ge 0} a_i$$$

When should you take points with $$$a_i \lt 0$$$? Rather, when should you not take points with $$$a_i \lt 0$$$?

1. Negative points which form a component consisting of only negative points should not be chosen at all.
2. They can never be chosen at the extremes of a component.
3. They can never be between two non-negative points points which are connected directly by an edge.

In all cases, removing such points will improve the answer without increasing the number of components.

Can you infer anything about pairs of non-negative points?

If a non-negative point is chosen, then any non-negative points connected to it by an edge should also be chosen. So if one such point is chosen, all non-negative points in its component must be chosen, otherwise none at all.

Why? Adding neighbouring non-negative points improves the answer without increasing the number of components.

So will you ever choose negative points between two non-negative points in the same component? Can you simplify the graph using Hints 2 and 3?

No. Ignore them. Replace each non-negative component with a single non-negative point equivalent to its sum and delete all the negative points that fall within any of these component.

Ok when should you take negative points then?

Consider two adjacent non-negative points not connected by an edge. Negative points between them can be chosen to connect them, i.e. reduce the number of connected components by $$$1$$$. Does this ring any bells?

How else can you reduce the number of components?

Delete (or un-choose) an entire connected component.

Is there a term in graph theory for something which reduces the number of components in a graph?

An edge.

Remodel this as another graph problem. What are the nodes? What are the edges? Do the edges have weights? What are the weights? What is the objective of the new problem?

You have some nodes (condensed non-negative components). There are two types of edges. Between every pair of these nodes adjacent by position in the original problem, you add an edge with weight equal to the cost of merging these two into the same component (minimum cost to pick some negative points between them such that they become connected). How do you calculate this value? And what about edges of the second type?

Lets see how to calculate these values first. Consider all the negative points between two adjacent nodes $$$l$$$ and $$$r$$$. Let $$$dp_j$$$ denote the absolute value of the sum of negative points chosen connecting $$$j$$$ with $$$l$$$ directly or indirectly. Then the weight of the edge between $$$l$$$ and $$$r$$$ will be the minimum value of $$$dp_j$$$ such that $$$j$$$ has a direct edge with $$$r$$$. This can be done in $$$\mathcal{O}(n)$$$ amortized using a stack or deque.

Next, think edges of the second type.

These edges correspond to deleting a component. Let's imagine there's a virtual $$$0$$$-th node. Add an edge between every node and the virtual node $$$0$$$ with weight equal to the total value of the component. Now what? How can you obtain the solution to the original problem from this setup?

As you might have guessed already, this is starting to look like an MST problem. Picking an edge reduces the number of components and the weights correspond to the cost of doing so. You want at most $$$k$$$ components. So in Kruskal fashion you can pick edges with the least cost until there are at most $$$k$$$ components.

But when you choose an edge, what changes in the rest of the graph?

What happens when you choose an edge of type $$$1$$$? You merge two nodes (components) into a single component. The new value of the component is the sum of the component values plus the edge weight. The two components' type $$$2$$$ edges are deleted and you add a new type $$$2$$$ edge for the merged component weighted with this value. The rest of the graph remains unchanged.

What happens when you choose an edge of type $$$2$$$? You are deleting a component $$$p_j$$$. If you want to merge components $$$p_{j-1}$$$ and $$$p_{j+1}$$$ (to its left and right) in the future, you'll have to add an edge of type $$$1$$$ between them. The weight of this edge is the sum of edge weights $$$(p_{j-1}, p_j)$$$ and $$$(p_j, p_{j+1})$$$ plus the value of the deleted component since picking these three will enable you to connect $$$p_{j-1}$$$ and $$$p_{j+1}$$$. This is also the minimum cost to connect them. Why?

So now you can handle the necessary updates to the graph every time you choose an edge. Just simulate Kruskal's algorithm until you have not more than $$$k+1$$$ components (accounting for the virtual node) and the final answer is $$$\sum\limits_{a_i \ge 0} a_i - \text{k-MST weight of the forest}$$$.

If it is not possible to connect some non-negative adjacent nodes, add an edge of weight $$$\infty$$$ between them for ease of implementation. You will never choose this weight.

Further, consider an array where odd indices $$$(i=1, 3, \ldots)$$$ contain the type $$$2$$$ weights corresponding to node $$$\left\lceil \frac{i}{2} \right\rceil$$$ and even indices $$$(i=2, 4, \ldots)$$$ contain the type $$$1$$$ weights corresponding to nodes $$$\left\lceil \frac{(i-1)}{2} \right\rceil$$$ and $$$\left\lceil \frac{(i+1)}{2} \right\rceil$$$. Now an update operation on $$$i$$$ is simply merging $$$(i-1, i, i+1)$$$ with value $$$a_{i-1} + a_{i+1} - a_i$$$ regardless of type of edge, further simplifying implementation.

The time complexity is $$$\mathcal{O}(n)$$$ to compute the initial type $$$1$$$ edge weights and make the reduction to the new graph. It is $$$\mathcal{O}(nlogn)$$$ to simulate Kruskal's with a heap or set.

Now you might be wondering why this will give you the optimal answer even though we do not consider all edges right from the start and 'discover' new ones during the process? What if there is an edge which is discovered later, but should have been picked earlier (smaller weight)?

It turns out that this is impossible. This is because any new weight you discover is always greater than or equal to the weight that was just chosen. So the non-decreasing order of edges weights chosen via the algorithm is preserved!