(This question is a variation of the LeetCode question 1525. Number of Good Ways to Split a String. If you haven't completed that question yet, it is recommended to solve it first.)
An analytics system measures how diverse the values are on both sides of an array split. Given an integer array arr, split it at a valid index into two non-empty contiguous parts.
For each index i where 1 ≤ i < arr.length, split arr into the non-empty parts arr[0...i - 1] and arr[i...arr.length - 1]. The score is the sum of the numbers of distinct integers in the two parts.
Return the maximum score among all valid splits. Your solution must run no worse than O(N) time, where N is the length of arr.
Constraints:
- 2 ≤
arr.length≤ 105 - -109 ≤
arr[i]≤ 109
Example 1:
Input: arr = [1, 2, 1, 3, 2] Output: 5 Explanation: Splitting at index 2 gives [1, 2] on the left and [1, 3, 2] on the right. They contain 2 and 3 distinct integers, respectively, so the score is 5.
Example 2:
Input: arr = [4, 1, 4, 2, 3, 2, 5, 1] Output: 7
Example 3:
Input: arr = [5, 5] Output: 2
