Untitled

import java.util.Arrays;

public class Solution {
    public int maxSatisfaction(int[] satisfaction) {
        // Sort the array in ascending order
        Arrays.sort(satisfaction);
        int n = satisfaction.length;
        // Initialize memoization array
        int[][] memo = new int[n][n + 1];
        for (int[] row : memo) {
            Arrays.fill(row, Integer.MIN_VALUE);
        }
        return dfs(0, 1, satisfaction, memo);
    }

    private int dfs(int index, int time, int[] satisfaction, int[][] memo) {
        // Base case: no more dishes to consider
        if (index == satisfaction.length) {
            return 0;
        }

        // Check if already computed
        if (memo[index][time] != Integer.MIN_VALUE) {
            return memo[index][time];
        }

        // Choice 1: Skip the current dish
        int skip = dfs(index + 1, time, satisfaction, memo);

        // Choice 2: Include the current dish
        int include = satisfaction[index] * time + dfs(index + 1, time + 1, satisfaction, memo);

        // Store the result in memo and return the maximum
        memo[index][time] = Math.max(skip, include);
        return memo[index][time];
    }
}