Max Distinct Counts After Splitting Array

Requirements

• You are given an integer array arr containing n elements.
• Select a split position i such that 1 <= i < n.
• The two resulting portions are left = arr[0:i] and right = arr[i:n].
• Return the greatest possible value of countDistinct(left) + countDistinct(right) among all permitted split positions.

Implement the following function:

def maxSum(arr):

Examples

Example 1

Input: arr = [1, 2, 1, 3]
Output: 4

Splitting after the first element gives 1 + 3 = 4, and splitting after the second gives 2 + 2 = 4; no split produces a larger sum.

Example 2

Input: arr = [6, 6, 6, 6]
Output: 2

Every non-empty side contains exactly one distinct value, so every valid split has a total of 1 + 1 = 2.

Example 3

Input: arr = [4, 9, 2, 7, 1]
Output: 5

All values are different, so a split after any position contributes the number of elements on the left plus the number on the right, totaling 5.

Constraints

• arr contains integers.
• The array has at least two elements, so at least one valid split exists.
• The split must leave both portions non-empty.