FastPrep
Problem · Dynamic Programming

Get Maximum

● MediumAmazonOA
See Amazon hiring insights

Amazon Fresh is a grocery store designed from the ground up to offer a seamless grocery shopping experience to consumers. As part of a stock clearance exercise at the store, given the number of fresh products, follow the rules given below to stack the products in an orderly manner.

  • There are a total of n piles of products.
  • The number of products in each pile is represented by the array numProducts.
  • Select any subarray from the array numProducts and pick up products from that subarray
  • The number of products you pick from the i-th pile is strictly less than the number of products you pick from the (i+1)th pile for all indices i of the subarray.

    • Find the maximum number of products that can be picked.

    Function Description

    Complete the function getMaximum in the editor.

    getMaximum has the following parameters:

    • int numProducts[n]: the number of products in each pile.

    Returns

    int: the maximum number of products that can be picked

    🧡 Much obliged, spike!! 🧡

    Examples
    01 · Example 1
    numProducts = [7, 4, 5, 2, 6, 5]
return = 12
    Example 1 illustration
    These are some ways strictly increasing subarrays can be chosen (1-based index): • Choose subarray from indices (1, 3) and pick products (3, 4, 5) respectively from each index, which is 12 products. Note that we are forced to pick only 3 products from index 1 as the maximum number of products we can pick from index 2 is 4, and we need to make sure that it is greater than the number of products picked from index 1. • Choose subarray from indices (3, 6) and pick products (1, 2, 4, 5) respectively from each index, which is 12 products. Similar to the above case, we are forced to pick only 1 product from index 3 as the maximum number of products at index 4 is only 2. • Choose subarray from indices (3, 5) and pick products [1, 2, 6] respectively from each index, which is 9 products. * Choose subarray from indices (1, 1) and pick all the 7 products. The max num of products is 12 :)
    02 · Example 2
    numProducts = [2, 9, 4, 7, 5, 2]
return = 16
    A few examples of how you can pick the products (1-based index): • Choose subarray from indices (1, 2) and pick products (2, 9) respectively from each index, which is 11 products. • Choose subarray from indices (1, 4) and pick products (2, 3, 4, 7), which is 16 products. • Choose subarray from indices (1, 5) and pick products (1, 2, 3, 4, 5), which is 15 products.
    03 · Example 3
    numProducts = [2, 5, 6, 7]
return = 20
    Take all the products as they already are in incresing order. (p.s. the source image is super blurry, I kinda think output is 20)
    Constraints
    • 1 ≤ n ≤ 5000
    • 1 ≤ numProducts[i] ≤ 10^9
    More Amazon problems
    drafts saved locally
    public int getMaximum(int[] numProducts) {
  // write your code here
}
    numProducts[7, 4, 5, 2, 6, 5]
    expected12
    sign in to submit