Array Java Coding Problems for Interviews

1.Maximum Product Subarray

Given an array Arr[] that contains N integers (may be positive, negative or zero). Find the product of the maximum product subarray.

Example 1:

Input:

N = 5

Arr[] = {6, -3, -10, 0, 2}

Output: 180

Explanation: Subarray with maximum product

is [6, -3, -10] which gives product as 180.

//Don't forget to add long long in max and min comparison

class Solution{
public:

// Function to find maximum product subarray
long long maxProduct(vector<int> arr, int n) {
long long int minPro=arr[0];
long long int maxPro=arr[0];
long long int ans=arr[0];
long long int choice1,choice2;
for(int j=1;j<n;j++){

choice1=arr[j]*minPro;
choice2=arr[j]*maxPro;
minPro=min((long long )arr[j],min(choice1,choice2));
maxPro=max((long long)arr[j],max(choice1,choice2));
ans=max(ans,maxPro);
}
return ans;
}
};

C++ Solution using Kadanes Algorithm

#define ll long long int
class Solution{
public:

// Function to find maximum product subarray
long long maxProduct(vector<int> arr, int n) {
ll maxProd = 1;
ll minProd = 1;
ll ans = 0;
for(int i =0 ; i<n ; i++){
ll x = arr[i];

if(x<0)
swap(minProd , maxProd);
maxProd = max(x , x*maxProd);
minProd = min(x , x*minProd);
ans = max(ans,maxProd);

}
return ans ;
}
};

class Solution {
// Function to find maximum product subarray
long maxProduct(int arr[], int n)
{
// Variables to store maximum and minimum
// product till ith index.
long minVal = arr[0];
long maxVal = arr[0];

long maxProduct = arr[0];
for (int i = 1; i < n; i++)
{
// When multiplied by -ve number,
// maxVal becomes minVal
// and minVal becomes maxVal.
if (arr[i] < 0)
{
long temp = maxVal;
maxVal = minVal;

minVal =temp;
}
// maxVal and minVal stores the
// product of subarray ending at arr[i].
maxVal = Math.max(arr[i], maxVal * arr[i]);
minVal = Math.min(arr[i], minVal * arr[i]);
// Max Product of array.
maxProduct = Math.max(maxProduct, maxVal);
}

// Return maximum product found in array.
return maxProduct;
}
}

This is the final answer

2.Longest consecutive subsequence

Given an array of positive integers. Find the length of the longest sub-sequence such that elements in the subsequence are consecutive integers, the consecutive numbers can be in any order.

Example 1:

Input:

N = 7

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

Output:

Explanation:

The consecutive numbers here

are 1, 2, 3, 4, 5, 6. These 6

numbers form the longest consecutive

subsquence.

int findLongestConseqSubseq(int arr[], int N)
{
int ans=0;
unordered_set<int>s;
int i=0,j=0;
for(i=0;i<N;i++)
{
s.insert(arr[i]);
}
for(i=0;i<N;i++)
{
if(s.find(arr[i]-1)==s.end())
{

int count =1;
while(s.find(arr[i]+count)!=s.end())
{
count++;
}
ans=max(ans,count);
}
}
return ans;
}
};

JAVA

static int findLongestConseqSubseq(int arr[], int N)
{
Arrays.sort(arr);
int j=arr[0];
int max=0;
int maxsofar=0;
for(int i=0;i<N;i++){
if(arr[i]==j){
j++;
max++;
}

else if(arr[i]!=j){
if(j<arr[i]){
max=1;
}
j=arr[i]+1;

}
if(max>maxsofar){
maxsofar=max;
}
}
return maxsofar;