maximum-score-of-a-node-sequence

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

There is an undirected graph with <code>n</code> nodes, numbered from <code>0</code> to <code>n - 1</code>.

You are given a 0-indexed integer array <code>scores</code> of length <code>n</code> where <code>scores[i]</code> denotes the score of node <code>i</code>. You are also given a 2D integer array <code>edges</code> where <code>edges[i] = [ai, bi]</code> denotes that there exists an undirected edge connecting nodes <code>ai</code> and <code>bi</code>.

A node sequence is valid if it meets the following conditions:

<ul>
	<li>There is an edge connecting every pair of adjacent nodes in the sequence.</li>
	<li>No node appears more than once in the sequence.</li>
</ul>

The score of a node sequence is defined as the sum of the scores of the nodes in the sequence.

Return the maximum score of a valid node sequence with a length of <code>4</code>. If no such sequence exists, return <code>-1</code>.

&nbsp;
Example 1:
<img alt="" src="https://assets.leetcode.com/uploads/2022/04/15/ex1new3.png" style="width: 290px; height: 215px;" />
<pre>
Input: scores = [5,2,9,8,4], edges = [[0,1],[1,2],[2,3],[0,2],[1,3],[2,4]]
Output: 24
Explanation: The figure above shows the graph and the chosen node sequence [0,1,2,3].
The score of the node sequence is 5 + 2 + 9 + 8 = 24.
It can be shown that no other node sequence has a score of more than 24.
Note that the sequences [3,1,2,0] and [1,0,2,3] are also valid and have a score of 24.
The sequence [0,3,2,4] is not valid since no edge connects nodes 0 and 3.
</pre>

Example 2:
<img alt="" src="https://assets.leetcode.com/uploads/2022/03/17/ex2.png" style="width: 333px; height: 151px;" />
<pre>
Input: scores = [9,20,6,4,11,12], edges = [[0,3],[5,3],[2,4],[1,3]]
Output: -1
Explanation: The figure above shows the graph.
There are no valid node sequences of length 4, so we return -1.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>n == scores.length</code></li>
	<li><code>4 &lt;= n &lt;= 5 * 104</code></li>
	<li><code>1 &lt;= scores[i] &lt;= 108</code></li>
	<li><code>0 &lt;= edges.length &lt;= 5 * 104</code></li>
	<li><code>edges[i].length == 2</code></li>
	<li><code>0 &lt;= ai, bi &lt;= n - 1</code></li>
	<li><code>ai != bi</code></li>
	<li>There are no duplicate edges.</li>
</ul>

maximumScore

Maximum Score of a Node Sequence

Get the Maximum Score

get-the-maximum-score

最大得分

Graph

Array

Enumeration

Sorting

给你一个&nbsp;<code>n</code>&nbsp;个节点的&nbsp;无向图&nbsp;，节点编号为&nbsp;<code>0</code>&nbsp;到&nbsp;<code>n - 1</code>&nbsp;。

给你一个下标从 0&nbsp;开始的整数数组&nbsp;<code>scores</code>&nbsp;，其中&nbsp;<code>scores[i]</code>&nbsp;是第 <code>i</code>&nbsp;个节点的分数。同时给你一个二维整数数组&nbsp;<code>edges</code>&nbsp;，其中&nbsp;<code>edges[i] = [ai, bi]</code>&nbsp;，表示节点&nbsp;<code>ai</code> 和&nbsp;<code>bi</code>&nbsp;之间有一条&nbsp;无向&nbsp;边。

一个合法的节点序列如果满足以下条件，我们称它是 合法的&nbsp;：

<ul>
	<li>序列中每&nbsp;相邻&nbsp;节点之间有边相连。</li>
	<li>序列中没有节点出现超过一次。</li>
</ul>

节点序列的分数定义为序列中节点分数之 和 。

请你返回一个长度为 <code>4</code>&nbsp;的合法节点序列的最大分数。如果不存在这样的序列，请你返回 <code>-1</code>&nbsp;。

&nbsp;

示例 1：

<img alt="" src="https://assets.leetcode.com/uploads/2022/04/15/ex1new3.png" style="width: 290px; height: 215px;" />

<pre>
输入：scores = [5,2,9,8,4], edges = [[0,1],[1,2],[2,3],[0,2],[1,3],[2,4]]
输出：24
解释：上图为输入的图，节点序列为 [0,1,2,3] 。
节点序列的分数为 5 + 2 + 9 + 8 = 24 。
观察可知，没有其他节点序列得分和超过 24 。
注意节点序列 [3,1,2,0] 和 [1,0,2,3] 也是合法的，且分数为 24 。
序列 [0,3,2,4] 不是合法的，因为没有边连接节点 0 和 3 。
</pre>

示例 2：

<img alt="" src="https://assets.leetcode.com/uploads/2022/03/17/ex2.png" style="width: 333px; height: 151px;" />

<pre>
输入：scores = [9,20,6,4,11,12], edges = [[0,3],[5,3],[2,4],[1,3]]
输出：-1
解释：上图为输入的图。
没有长度为 4 的合法序列，所以我们返回 -1 。
</pre>

&nbsp;

提示：

<ul>
	<li><code>n == scores.length</code></li>
	<li><code>4 &lt;= n &lt;= 5 * 104</code></li>
	<li><code>1 &lt;= scores[i] &lt;= 108</code></li>
	<li><code>0 &lt;= edges.length &lt;= 5 * 104</code></li>
	<li><code>edges[i].length == 2</code></li>
	<li><code>0 &lt;= ai, bi &lt;= n - 1</code></li>
	<li><code>ai != bi</code></li>
	<li>不会有重边。</li>
</ul>