Problem Link - Maximum Score in Greedy Algorithms
Problem Statement:
We are tasked with selecting one element from each row of an N x N matrix, where the elements picked must strictly increase as we move from the first row to the last row. The goal is to maximize the sum of the selected elements. If it’s not possible to select such elements, the output should be -1.
Approach:
1. Sort Each Row: Start by sorting each row of the matrix. This ensures that when we pick elements from the rows, we can efficiently choose the maximum possible element from the current row that satisfies the strictly increasing condition.
2. Pick Maximum Element with Constraints:
- We initialize by selecting the maximum element from the last row.
- Then, for each row before the last (moving backward), we select the largest element that is smaller than the previously chosen element from the next row (to maintain the strictly increasing condition).
- If at any row, it’s impossible to find such an element, we mark the solution as invalid and print
-1.
3. Continue or Break: If a valid selection of elements is found (i.e., elements strictly increase as we move up), we compute the sum and print it. Otherwise, print -1.
Complexity:
- Time Complexity: Sorting each row takes
O(N log N). Finding the maximum element in the row smaller than the previously chosen element takesO(N). So, the overall time complexity isO(N^2 log N). - Space Complexity:
O(1)