FastPrep
Problem · Matrix

Get Maximum Sum

Learn this problem
● MediumAmazon logoAmazonNEW GRADOA
See Amazon hiring insights

Problem statement

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 ith 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

getMaximumSum(data: int[][], factor: int[], x: int) → long

Complete the function getMaximumSum in the editor.

getMaximumSum has the following parameters:

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

Returns

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

📣 💪spike👍 rocks! 🌟

Examples

Example 1

data = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]factor = [1, 2, 1]x = 2return = 15
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

More Amazon problems

drafts saved locally
public long getMaximumSum(int[][] data, int[] factor, int x) {
  // write your code here
}
data[[1, 2, 3], [4, 5, 6], [7, 8, 9]]
factor[1, 2, 1]
x2
expected15
checking account