Want to solve **Find max products Amazon OA 2023?, **if yes then this article is for you.

Make sure you check the List of Amazon OA questions in the year of 2022 and 2023. Today, we are going to see another problem from amazon oa called *Find max products* which was asked in 2022, this questions might be still active in some of the **Amazon OA** so save all the solutions, now lets see how can we solve this problem.

Contents

**Find max products Amazon OA 2023 Solution**

Amazon Fresh is a new 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 many piles 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 such that the number of products you pick from the 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.

**Example**

The numbers of products in each pile are numProducts = [7, 4, 5, 2, 6, 5].

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 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 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 maximum number of products is 12.

**Function Description**

Complete the function findMaxProducts in the editor below.

findMaxProducts 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

**Constraints**

- 1 ≤ n ≤5000
- 1 ≤ numProducts[i] <10
^{9}

**Input**

```
STDIN FUNCTION
------- -------------
6 -> numProducts[] size n = 6
2 -> numProducts = [2, 9, 4, 7, 5, 2]
9
4
7
5
2
```

**Output**

16

**Explanation**

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.

**Related: Google Online Assessment 2022 Questions List**

**SOLUTION**

**Program: Find max products Amazon OA Solution** in Java

**Explanation:** Using DP

The idea is very simple, simulate what we would do if we were doing this manually.

- Pick any pile to start with. Pick any number of products in that pile and move to the next one.
- Based on the number you picked from the previous pile, you can either pick a bigger number of products from the current pile or pick 0 if available products are less than what you picked from the previous pile.
- Repeat this process until you find a combination subarray of piles that give you the max products possible.

Using memoization to avoid doing unnecessary work, the idea is that for each pile, the max number of products you can pick is dependent on how many you picked in the previous pile, so when we calculate the max for a pile, we can save that like memo [pileIndex] [previousPileProductsCount] = max-we-can-pick-from-current-pile.

```
public static void main(String[] args) {
int[] piles = new int[] { 7, 4, 5, 2, 6, 5 };
// initialize the memo, this code could be simplified by using a map
int maxPile = 0;
for (var pile : piles) {
maxPile = Math.max(maxPile, pile);
}
int n = piles.length;
int[][] memo = new int[n][maxPile];
for (int i = 0; i < n; i++) {
Arrays.fill(memo[i], -1);
}
// go through the piles one by one, and find the max we can get if
// we started at said pile
int max = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
max = Math.max(max, dfs(piles, i, 0, memo));
}
System.out.println(max);
}
private static int dfs(int[] piles, int index, int prevPileContribution, int[][] memo){
/**
* Our dfs termination conditions:
* 1. we reached the end of piles array.
* 2. current pile products is less than or equal to what we picked from previous pile.
* 3. we have calculated the max for this pile before given the same amount picked from the previous pile
* */
if(index == piles.length) return 0;
if(piles[index] <= prevPileContribution) return 0;
if(memo[index][prevPileContribution] != -1) return memo[index][prevPileContribution];
int pileMax = 0;
/**
* loop through the products in this pile from
* min = products picked from previous pile +1
* max = the max products available in this pile
*/
for(int i=prevPileContribution+1; i<= piles[index]; i++){
int tempMax = i+ dfs(piles, index+1, i, memo);
pileMax = Math.max(pileMax, tempMax);
}
// store the max we can pick from this pile given what we picked from previous pile
memo[index][prevPileContribution] = pileMax;
return pileMax;
}
```

**Program: Find max products Amazon OA Solution** in Python

Using DP. Not sure if this will work. The time complexity will be O(max(product)*n).

```
def amazon_fresh(products):
@lru_cache(None)
def dp(i, prev):
if i == len(products):
return 0
product = products[i]
if product < prev:
return 0
ans = dp(i + 1, prev)
for j in range(products[i], -1, -1):
if j > prev:
ans = max(dp(i + 1, j)+j, ans)
return ans
return dp(0, 0)
```

**Program: Find max products Amazon OA Solution** in C++

```
int solve(vector<int> arr){
int res = 0;
vector<int> darr(arr.size());
darr[arr.size()-1] = arr[arr.size()-1];
for(int i = arr.size()-2; i>=0;i--){
if(arr[i] <arr[i+1]){
darr[i] = arr[i];
}else{
darr[i] = arr[i+1]-1;
}
if(darr[i] == 0){
darr[i] = arr[i];
}
}
int sum = arr[0];
for(int i=1;i<arr.size();i++){
if(arr[i]<arr[i-1]){
res = max(res,sum);
sum=arr[i];
}else{
sum+=arr[i];
}
}
res = max(res,sum);
sum = darr[0];
for(int i=1;i<darr.size();i++){
if(darr[i]<darr[i-1]){
res = max(res,sum);
sum=darr[i];
}else{
sum+=darr[i];
}
}
res = max(res,sum);
return res;
}
int main()
{
vector<int> arr = {7,4,5,2,6,5};
int res = solve(arr);
cout<<res<<endl;
return 0;
}
```

**Amazon OA 2023 Questions** **with Solution**

- Shopping Patterns Solution Amazon OA 2023
- Reorder Data in Log Files Solution Amazon OA 2023
- Top K Frequent Words Solution Amazon OA 2023
- Trees Height Solution Amazon OA SDE 2023
- Counting Binary Substrings Amazon OA 2023
- Grid Connections Amazon OA 2023
- Shipment Imbalance Amazon OA 2023
- Max Profit Amazon OA 2023
- Find Lowest Price Amazon OA 2023
- Decode String Frequency Amazon OA 2023
- Simple Cipher Amazon OA 2023
- Valid Discount Coupons Amazon OA 2023 Solution
- Count Maximum Teams Amazon OA 2023
- Minimum Coin Flips Amazon OA 2023
- Max Average Stock Price Amazon OA 2023 Solution
- Robot Bounded In Circle Amazon OA 2023
- Shopping Options Amazon OA 2023 Solution
- Fill The Truck Maximum Units on a Truck Amazon OA Solution
- Maximize Score After N Operations Number Game Solution Amazon OA 2023
- Slowest Key Amazon OA 2023 Solution
- Five Star Seller Maximum Average Pass Ratio Amazon OA 2023
- Split String Into Unique Primes Amazon OA 2023 Solution
- Storage Optimization Amazon OA 2023 Solution
- Minimum Difficulty of a Job Schedule Amazon OA 2023 Solution
- Autoscale Policy Utilization Check Amazon OA 2023
- Optimal Utilization Solution Amazon OA 2023
- Merge Two Sorted Lists Solution Amazon OA 2023
- Two Sum Unique Pairs Solution Amazon OA 2023
- Amazon Music Pairs Amazon OA 2023 Solution
- Class Grouping Amazon OA 2023 Solution
- Get encrypted number Amazon OA 2023 Solution
- Find Total Imbalance Amazon OA 2023 Solution
- Find Total Power Amazon OA 2023 Solution

def findMaxProducts(array):

if not array:

return 0

i = 0

currentMaxProducts = 0

while i < len(array):

candidateMaxProducts, i = recursiveHelper(i, 0, array)[0], recursiveHelper(i, 0, array)[1]

currentMaxProducts = max(currentMaxProducts, candidateMaxProducts)

return currentMaxProducts

def recursiveHelper(currentIdx, prevElement, array):

if currentIdx == len(array):

return (0, currentIdx) # next starting point

currentProducts = array[currentIdx]

if currentProducts <= prevElement:

return (0, currentIdx) # next starting point

maxProducts = 0

maxDepthReached = 0

for currentProductCount in range(prevElement + 1, currentProducts+1):

result = recursiveHelper(currentIdx + 1, currentProductCount, array)

candidateMax = currentProductCount + result[0]

maxProducts = max(candidateMax, maxProducts)

maxDepthReached = max(result[1], maxDepthReached)

return (maxProducts, maxDepthReached)

print(findMaxProducts([2,9,4,7,5,2]))

# DP Solution

def findMaxProducts(array):

if not array:

return 0

i = 0

currentMaxProducts = 0

memo = [[None for _ in range(max(array)+1)] for _ in range(len(array))]

while i < len(array):

candidateMaxProducts = recursiveHelper(i, 0, array, memo)

currentMaxProducts = max(currentMaxProducts, candidateMaxProducts)

i += 1

return currentMaxProducts

def recursiveHelper(currentIdx, prevElement, array, memo):

if currentIdx == len(array):

return 0

currentProducts = array[currentIdx]

if currentProducts <= prevElement:

return 0

if memo[currentIdx][prevElement] is not None:

return memo[currentIdx][prevElement]

maxProducts = 0

minDepthReached = len(array)

for currentProductCount in range(prevElement + 1, currentProducts+1):

result = recursiveHelper(currentIdx + 1, currentProductCount, array, memo)

candidateMax = currentProductCount + result

maxProducts = max(candidateMax, maxProducts)

memo[currentIdx][prevElement] = maxProducts

return maxProducts

print(findMaxProducts([7,4,5,2,6,5]))