Beats 100% of the Java users
Intuition\n1. Maximize the Score: The goal is to maximize the score by selecting rows such that the sum of selected values is the highest possible.\n\n2. Greedy
# Intuition\n1. Maximize the Score: The goal is to maximize the score by selecting rows such that the sum of selected values is the highest possible.\n\n2. Greedy by Value: Start with the highest possible value and attempt to include rows where this value occurs. Use recursive exploration to find the optimal combination of rows for each value.\n\n3. Backtracking: Explore different subsets of rows to ensure that you consider all possible ways to maximize the score. This includes trying to include each row for the current value and backtracking if necessary.\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n1. Preprocess Grid Data:\n\nTraverse the grid to populate maxElementPosition, an array of lists where each index represents a value, and the list contains row indices where that value occurs. This preprocessing helps in quickly accessing which rows contain a specific value.\n\n2. Recursive Exploration:\n\nUse a recursive function (solve) to explore the combinations of rows for each value from the highest to the lowest.\n\nFor each value, attempt to include rows where the value occurs. This involves marking the row as visited and making a recursive call to continue with the next lower value and remaining rows.\n\nAfter exploring a row, backtrack by unmarking the row to explore other combinations.\n\nTrack the maximum score found during these explorations.\n\n3. Backtracking for Combinations:\n\nIf no valid rows are found for a current value, continue to the next lower value without including any row for the current value.\n\nThis ensures that all potential combinations of rows are explored to find the optimal solution.\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: O(2^m * m * n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:  O(m * k)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```java []\nimport java.util.*;\n\nclass Solution {\n    // Main function to calculate the maximum score\n    public int maxScore(List<List<Integer>> grid) {\n        // Array to store the positions of rows where each value occurs\n        List<Integer>[] maxElementPosition = new List[101];\n\n        // Initialize the array with empty lists\n        for (int i = 0; i < 101; i++) {\n            maxElementPosition[i] = new ArrayList<>();\n        }\n        \n        int m = grid.size(); // Number of rows\n        int n = grid.get(0).size(); // Number of columns\n        int max = 0; // Variable to keep track of the maximum score\n\n        // Populate the maxElementPosition array with row indices for each value\n        for (int i = 0; i < m; i++) {\n            for (int j = 0; j < n; j++) {\n                int val = grid.get(i).get(j);\n                max = Math.max(max, val); // Update the maximum value found\n                if (!maxElementPosition[val].contains(i)) {\n                    maxElementPosition[val].add(i); // Add row index for the value\n                }\n            }\n        }\n\n        // Boolean array to keep track of visited rows\n        boolean[] vis = new boolean[m];\n\n        // Start solving with the maximum value, total rows, and initial score of 0\n        return solve(maxElementPosition, max, m, vis, 0);\n    }\n\n    // Recursive function to find the maximum score\n    private int solve(List<Integer>[] maxElementPosition, int currEle, int remainingRows, boolean[] vis, int score) {\n        // Base case: if current element is non-positive or no rows remaining, return score\n        if (currEle <= 0 || remainingRows == 0) return score;\n\n        // Skip elements with no rows\n        while (currEle >= 1 && maxElementPosition[currEle].isEmpty()) {\n            currEle--;\n        }\n\n        // Get the list of row indices for the current element\n        List<Integer> rowsInd = maxElementPosition[currEle];\n        int maxScore = score; // Initialize max score for the current state\n        boolean found = false; // Flag to check if any row was found\n\n        // Try to include each row for the current element\n        for (int row : rowsInd) {\n            if (!vis[row]) {\n                vis[row] = true; // Mark row as visited\n                found = true; // Found at least one valid row\n                // Recursively solve for the next element, reducing the remaining rows\n                maxScore = Math.max(maxScore, solve(maxElementPosition, currEle - 1, remainingRows - 1, vis, score + currEle));\n                vis[row] = false; // Backtrack: unmark row\n            }\n        }\n\n        // If no valid row was found for the current element, continue without including it\n        if (!found) {\n            maxScore = Math.max(maxScore, solve(maxElementPosition, currEle - 1, remainingRows, vis, score));\n        }\n\n        return maxScore; // Return the maximum score found\n    }\n}\n\n```
['Java']