Dynamic Programming HACKER EARTH questions

Here we will see HACKER EARTH and HACKER RANK dynamic coding questions asked in various off campus recruitments.

Question: MAXIMUM PRODUCT

You are given an array A of size N

You are given Q queries of the following form

1LR: Find the maximum product of “two integers” in the sub array starting from index L and ending at index R (L and R inclusive)
2LR: Find the maximum product of “three integers” in the sub array starting from index L and Ending at index R (L and R inclusive).

Task:

print the required maximum product for each type of query.

Example:

Assumptions

T=1
N=5
Q=2
A={1,3,4,-2,5}
queries=[{1,1,3},{2,3,5}]

Approach:

The subarray for the first query is [1,3,4] as the query is of the first type you need to find the maximum product of two integers. The only possible products are 3(1*3), 12(3*4) and 4(1*4). Here as 12 is the maximum possible product so 12 is the output for first sub query.
The subquery for second query is [4,-2,5] as the query is of the second type. we need to find the maximum product of “three integers “. The only possible roduct is -40 (4*(-2)*5) so the output will be -40

Function Discription:

N represents the length of the array A
Q represents the number of queries
A represents the given array
Queries : represents the queries array , where each query contains 3 elements
1. The first integer is either 1 or 2, where 1 is denoting query of the first type and 2 is denoting the query of second type
2. The second integer represents the starting index L of the subarray
3. The third intger represents the ending index of the subarray.

Example2:

Input:

N=5

Q=3

A={2,4,-2,-2,3,7}

Queries=[{1,4,6},{2,3,5},{1,2,3}]

Output:

-8

Approach: It remains same as that of the previous example.

Alogorithm to solve

Initially take all inputs from user like value of N,Q, array A and Queries array.
Use 2 for loops for iterating through elements of 2D aray
First check if the first value in first sub query is 1 or not. If it is 1 then,
create an ARRAYLIST <Integer> of type integers starting from index mentioned in problem and ending at specified index
then sort the arraylist in “Decending order“
Then print the product of first two elements as answer.
If the first element in sub query is 2 then,
create an ARRAYLIST of integer types starting from index mentioned in problem and ending at specified index
then sort the arraylist in “Decending order“
Then print the product of first three elements as answer.

JAVA CODE

package arrayproblems;
import java.util.*;
class Problem23 {
	public static void main(String[] args) {
		
		
		// Code by VRASHIKESH PATIL 
		
		int N=5;
		int Q=3;
		int[] array1= {2,4,-2,-2,3,7};
		int[][]	array2= {{1,4,6},{2,3,5},{1,2,3}};
		
		for(int i=0;i<array2.length;i++) {
			
			for(int j=0;j<array2[i].length;j++) {
				
				if(array2[i][j]==1) {
					ArrayList<Integer> array3=new ArrayList<Integer>();
					
					
					for(int k=array2[i][j+1]-1;k<array2[i][j+2];k++) {
						
						array3.add(array1[k]);
					}
					
					Collections.sort(array3,Collections.reverseOrder());
					System.out.println(array3.get(0)*array3.get(1));
					break;
				}
				else if(array2[i][j]==2) {
					ArrayList<Integer> array3=new ArrayList<Integer>();
					for(int k=array2[i][j+1]-1;k<array2[i][j+2];k++) {
						array3.add(array1[k]);
						
					}
					Collections.sort(array3,Collections.reverseOrder());
					System.out.println(array3.get(0)*array3.get(1)*array3.get(2));
					break;
				}	
			}
		}
	}	
}

Watch Step by Step Explanation for Above Code on our Channel

Watch Now

Similar Off Campus Coding Problems

APPSIAN off Campus Coding Question

Maximum Work Hacker Earth Problem solved

Count Buildings Hacker Earth coding question with solution

SHL off campus coding questions

Beginner’s friendly top 5 array questions in java