FastPrepFastPrep
Problem Brief

Get Maximum Sum

NEW GRADOA
See Amazon online assessment and hiring insights

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 Description

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! 🌟

1Example 1

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

Limits and guarantees your solution can rely on.

  • 1 ≤ n ≤ n ≤ 1000
  • 1 ≤ data[i][j] ≤ 10^9
  • 1 ≤ factor[i] ≤ n
public long getMaximumSum(int[][] data, int[] factor, int x) {
  // write your code here
}
Input

data

[[1, 2, 3], [4, 5, 6], [7, 8, 9]]

factor

[1, 2, 1]

x

2

Output

15

Sign in to submit your solution.