180. Unique Stretch Score
A museum places a numbered souvenir token on every stall along a long corridor, and the array nums lists the value stamped on each token, in stall order. A visitor walks past a run of consecutive stalls and collects the token from every stall in that run. The museum has one rule: a visitor must never end up holding two tokens that carry the same value.
Return the largest total value a visitor can collect in one walk, that is, the maximum sum of a contiguous part of nums in which all values are different. The walk must cover at least one stall.
Example 1
- Input:
- nums = [4,2,4,5,6]
- Output:
- 17
- Explanation:
The walk
[2,4,5,6]has all-different values and totals 17. Starting at the first stall fails at the second 4, so 17 is the best.
Example 2
- Input:
- nums = [3,3,3]
- Output:
- 3
- Explanation:
Every walk of two or more stalls repeats the value 3, so the best is a single token worth 3.
Example 3
- Input:
- nums = [5,3,1,3,5]
- Output:
- 9
- Explanation:
Both
[5,3,1]and[1,3,5]are all-different and total 9; no longer run avoids a repeat.
Constraints
1 ≤ nums.length ≤ 105
1 ≤ nums[i] ≤ 104
The answer always fits in a 32-bit signed integer.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 4,000 msC++ 1,000 msJava 2,000 msJavaScript 2,000 msTypeScript 2,000 ms
Expected complexity
- Time
- O(n)
- Space
- O(U)