FastPrep

Description

Solutions

Get Maximum Sum

👩‍🎓 NEW GRAD📚RELATED PROBLEMS

Note 📝 - might be a sister problem of Get Maximum Sum 🦭

Developers at Amazon are working on a prototype for a utility that compresses a n x n matrix, data, with the help of a compression rate represented by an array, factor. The utility returns an integer which is the maximum sum of exactly x elements of the matrix such that the number of elements taken from the i^th row does not exceed factor[i] for all 0 <= i < n. The utility returns -1 if the compression cannot be performed.

Given arrays data and factor, find the maximum sum to perform compression under the given constraints, or -1 if it is not possible.

Function Description

Complete the function getMaximumSum in the editor.

getMaximumSum has the following parameters:

int factor[n]: the rate of compression for each element of data
int data[n][n]: the square matrix of data
int x: the number of elements to choose

Returns

long int: the maximum sum of health of the selected servers

📣 💪spike👍 rocks! 🌟

Example 1:

Input:  data = [[1, 2, 3], [4, 5, 6]], factor = [1, 2, 1], x = 2
Output: 15 
Explanation:
The best choices for each row are (3), (5, 6), and (9), respective. Only x = 2 elements can be chosen. The maximum sum of 2 elements is a[2][2] + a[1][2] = 9 + 6 = 15. So, return 15 👆✋

Constraints:

1 ≤ n ≤ n ≤ 1000
1 ≤ data[i][j] ≤ 10^9
1 ≤ factor[i] ≤ n