FastPrep
Problem · Dynamic Programming

Get Maximum Sum Arr (Fungible :)

Learn this problem
● HardAmazonFULLTIMEOA
See Amazon hiring insights

Problem statement

At Amazon, the team at the fulfillment center is responsible for the packaging process. There is an array, item_weights, of n items to pack. The team needs to create a new array, new_arr, by removing exactly n/3 items from item_weights without changing the order of those remaining.

- The sum_arr of array new_arr is defined as the sum of the weights or elements in the first half of the array minus the sum of the weights in the second half of the array. - Given n items and an array item_weights, find the maximum sum_arr possible.

Function

getMaxSumArr(item_weights: int[]) → int

Complete the function getMaxSumArr in the editor below.

getMaxSumArr has the following parameters:

  1. int item_weights[n]: item weights

Returns

int: the maximum possible sum_arr

Examples

Example 1

item_weights = [3, 2, 1]return = 2
Example 1 illustration

Example 2

item_weights = [1, 3, 4, 7, 5, 2]return = 4
Given n = 6, item_weights=[1, 3, 4, 7, 5, 2], remove the elements 1, 3 to leave new_arr=[4, 7, 5, 2], hence the sum will be (4+7)-(5+2) = 4.

Constraints

  • 3 ≤ N ≤ 10^5
  • -10^4 ≤ item_weights[i] ≤ 10^4
  • n is divisible by 3

    • More Amazon problems

    drafts saved locally
    public int getMaxSumArr(int[] item_weights) {
  // write your code here
}
    item_weights[3, 2, 1]
    expected2
    checking account