Finding the maximum sum of the number of distinct elements in an array after splitting it into K subarrays

Vasya has planted N trees in a line. The type of k-th tree is T_k. Mainak wants to create M gardens by building M−1 walls between the trees so that the tree line is splitted into M line segments each being a separate garden. Note that some gardens may contain no tree.

"Beauty" of a garden is equal to the number of distinct tree types in it. What is the maximal possible total "beauty" of the gardens?

Constraints:
1 <= N <= 5000
1 <= M <= 100
1 <= T_k <= 10^9

Time limit: 2 seconds

Example input:
7 4
4 7 4 1 2 4 2

Example output:
7

Hello StackOverflow people!

I'm stuck on this competitive programming question, and I've been working on it for quite a while now, but I can't come up with a solution that fits to the constraints.

I have coded a solution based on this idea mentioned in this GeeksforGeeks post.

But it was too slow to fit in the constraints. You can check out my solution below.

I precomputed the distinct elements in the [l, r] subarrays in the segments array so I could use it later on. Then I used a dynamic programming approach to build up the DP table but it was just too slow.

I thought about using binary search but I couldn't figure out how to do that since the question asks for the total number of distinct values and there isn't a constraint on the maximum number of distinct elements in one subarray referring to this post.

Any help would be appreciated at this point because I really can't see how to approach this problem other than DP.

#include <bits/stdc++.h>
using namespace std;

int main() {
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        int n, m; cin >> n >> m;
        m--;

        int a[n];
        int dp[n+5][m+5];
        memset(dp, 0, sizeof(dp));

        for (int i = 0; i < n; i++) cin >> a[i];

        int segments[n][n];

        for (int i = 0; i < n; i++) {
                unordered_set<int> s;
                for (int j = i; j < n; j++) {
                        s.insert(a[j]);
                        segments[i][j] = s.size();
                }
        }

        for (int i = n-1; i >= 0; i--) {
                 for (int j = 0; j <= m; j++) {
                        for (int k = i; k < n; k++) { 
                                if (j > 0) dp[i][j] = max(dp[i][j], segments[i][k] + dp[k+1][j-1]);
                                else dp[i][j] = segments[i][k];
                        }
                 }
        }
        cout << dp[0][m];
        return 0;
}