FastPrep
Problem · Dynamic Programming

Maximum Number of Products You Can Pick

Learn this problem
● HardAmazonOA
See Amazon hiring insights

Problem statement

You have an array of products, where each element contains how much product you have products = [2, 9, 4, 7, 5, 3]. Pick a subarray of products. Starting from the beginning of the subarray, pick some number of products. One restriction: the number of products you pick have to be strictly increasing.

For example, you choose [7, 5, 3], you pick 4 products out of 7, 5 out of 5, there's nothing to pick from [3]. But you can pick [1, 2, 3], a total of 6 products.

The ask is to find the maximum number of products you can pick. The answer for the above example is 16. Because you pick [2, 9, 4, 7] subarray and [2, 3, 4, 7] products out of it.

Constraints:

  • 1 <= len(products) <= 5000 the array length won't exceed 5000
  • 1 <= products[i] <= 10^9, the stocks per product won't exceed 10^9

Function

maximumProductsPicked(products: int[]) → int

Complete the function maximumProductsPicked in the editor.

maximumProductsPicked has the following parameter:

  1. int[] products: an array of integers representing the stock of each product

Returns

int: the maximum number of products you can pick

Examples

Example 1

products = [2, 9, 4, 7, 5, 3]return = 16

The optimal subarray to pick from is [2, 9, 4, 7]. You can pick the following number of products:

  • From the first product: 2
  • From the second product: 3 (since it must be strictly more than the previous pick)
  • From the third product: 4 (since it must be strictly more than the previous pick)
  • From the fourth product: 7 (since it must be strictly more than the previous pick)
The total number of products picked is 2 + 3 + 4 + 7 = 16.

More Amazon problems

drafts saved locally
public int maximumProductsPicked(int[] products) {
    // write your code here
}
products[2, 9, 4, 7, 5, 3]
expected16
checking account