Untitled

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class UnequalElements2 {

    private int n;
    private int[][] dp;
    private int[] nextSame;
    private int[][] data;


    private static class Pair {
        int value;
        int count;

        Pair(int value, int count) {
            this.value = value;
            this.count = count;
        }
    }

    private void processData(int[] arr) {
        List<Pair> dataList = new ArrayList<>();
        int st = 0;

        for (int i = 1; i < arr.length; i++) {
            if (arr[i] != arr[i - 1]) {
                dataList.add(new Pair(arr[i - 1], i - st));
                st = i;
            }
        }
        dataList.add(new Pair(arr[arr.length - 1], arr.length - st));

        // Convert the List<Pair> to an array
        data = new int[dataList.size()][2];
        for (int i = 0; i < dataList.size(); i++) {
            data[i][0] = dataList.get(i).value;
            data[i][1] = dataList.get(i).count;
        }

        // Calculate the next occurrence
        n = data.length;
        nextSame = new int[n];
        Map<Integer, Integer> seen = new HashMap<>();
        for (int i = n - 1; i >= 0; i--) {
            int value = data[i][0];
            nextSame[i] = seen.getOrDefault(value, n);
            seen.put(value, i);
        }

    }

    private int recursion(int i, int k) {
        if (k < 0) return 0;
        if (i == n) return 0;

        if (dp[i][k] != -1) return dp[i][k];

        // Choose the current element
        int ans = Math.max(recursion(i + 1, k - 1), recursion(nextSame[i], k)) + data[i][1];
        // Not choosing the current element
        ans = Math.max(ans, recursion(i + 1, k));

        dp[i][k] = ans;
        return ans;
    }

    public void solve(int[] arr, int k) {
        processData(arr);
        dp = new int[n][k + 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= k; j++) {
                dp[i][j] = -1;
            }
        }
        System.out.println("ans2 " + recursion(0, k));
    }

    public static void main(String[] args) {
        int[] arr = {1, 1, 2, 3, 2, 2, 1, 1};
        int k = 2;
        UnequalElements2 app = new UnequalElements2();
        app.solve(arr, k);
    }
}