CostMaximizer

You are given 2*N nodes. For each i (1 <= i <= N) there is a red node number i and a blue node number i.

Each pair of nodes is connected by an edge. For nodes i and j of the same colour this edge has weight wt(i,j). For nodes i and j of the opposite colour this edge has weight K - wt(i,j).

The value K is the same for all pairs i, j. For each edge, the value K will satisfy the following: wt(i,j) <= K <= 2*wt(i,j).

You must select exactly N out of these nodes: for each number either the red node or the blue node, but not both. Among those, you must select at least one red node and at least one blue node.

Determine and return the largest possible sum of weights in the complete graph formed by the nodes you selected and all edges between them.

You are given the ints N and K mentioned above and a int[] w with the upper triangle of the weights matrix.

You can reconstruct the whole matrix as follows:

int k = 0;
for (int i=1; i<=N; ++i) for (int j=i+1; j<=N; ++j) {
    wt(i,j) = wt(j,i) = w[k];
    ++k;
}