Amazon OA

Round 1

Questions: Recently saw this question in Amazon SDE OA, feels like using DP but cannot think of solution, especially do we need to consider removing items not connected?

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 Description

Complete the function getMaxSumArr in the editor below.

getMaxSumArr has the following parameters:

int item_weights[n]: item weights
Returns

int: the maximum possible sum_arr

Example 1:
Input: item_weights = [3, 2, 1]
Output: 2

Example 2:
Input: item_weights = [1, 3, 4, 7, 5, 2]
Output: 4

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