Untitled

import java.util.*;

public class BoxColoring {
    public static int minimumColorsNeeded(List<Integer> boxes, int s) {
        int n = boxes.size();
        int[] dp = new int[n];

        for (int i = 0; i < n; i++) {
            int min = boxes.get(i), max = boxes.get(i);
            dp[i] = i + 1;

            for (int j = i; j >= 0; j--) {
                min = Math.min(min, boxes.get(j));
                max = Math.max(max, boxes.get(j));

                if (i - j + 1 > dp[i]) {
                    break;
                }

                if (max - min <= s) {
                    dp[i] = Math.min(dp[i], (j > 0 ? dp[j - 1] : 0) + 1);
                }
            }
        }

        return dp[n - 1];
    }

    public static void main(String[] args) {
        List<Integer> boxes = new ArrayList<>(Arrays.asList(1, 3, 1, 2, 4, 2, 1));
        int s = 2;

        int result = minimumColorsNeeded(boxes, s);
        System.out.println(result); // Output: 3
    }
}