Maximize Segment Diversity

Easy

0/40

Contributed by

0 upvote

Problem statement

You are a market analyst tasked with studying customer purchase data to identify periods of high product diversity. You are given a sequence of purchases, A, where each element is a product_id.

To analyze this data, you must split the entire sequence into exactly K continuous, non-empty "time windows" (segments).

The "diversity score" of a single time window is defined as the number of unique product_ids it contains. Your goal is to find a way to split the purchase history into K windows such that the sum of the diversity scores of all windows is maximized.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains two space-separated integers, N (the number of purchases) and K (the number of windows).

The second line contains N space-separated integers, representing the sequence of product_ids.

Output Format:

The output should be a single integer representing the maximum possible total diversity score.

Note:

Each of the K segments must be a non-empty, contiguous block of the original array.

The K segments, when placed together, must form the complete original array.

Sample Input 1:

5 2
1 1 2 1 3

Sample Output 1:

Explanation for Sample 1:

We need to split [1, 1, 2, 1, 3] into 2 windows. Let's check some options:
 Split 1: [1, 1] | [2, 1, 3]
 - Value of [1, 1]: 1 unique element (1).
 - Value of [2, 1, 3]: 3 unique elements (1, 2, 3).
 => Total Score = 1 + 3 = 4.

 Split 2: [1, 1, 2, 1] | [3]
 - Value of [1, 1, 2, 1]: 2 unique elements (1, 2).
 - Value of [3]: 1 unique element (3).
 => Total Score = 2 + 1 = 3.

 The maximum possible score is 4.

Sample Input 2:

4 3
1 2 1 2

Sample Output 2:

Explanation for Sample 2:

We need to split [1, 2, 1, 2] into 3 windows. The optimal split is:

Split: [1] | [2] | [1, 2]
- Value of [1]: 1.
- Value of [2]: 1.
- Value of [1, 2]: 2.
=> Total Score = 1 + 1 + 2 = 4.

Expected Time Complexity:

The expected time complexity is O(K * N^2).

Constraints:

1 <= K <= N <= 2000
1 <= A[i] <= N

Time limit: 2 sec

Approaches (1)

Approach 1

Dynamic Programming

Time Complexity

Space Complexity

(100% EXP penalty)

Maximize Segment Diversity

Console