Microsoft Interview Question Software Engineers
Country: United States
It fails for the following inputs
{ 5, 50, 6, 35, 0, 1, 2, 7, 45, 4, 30, 40, 41, 60, 3 });
{ 6, 50, 7, 35, 1, 2, 3, 8, 45, 5, 30, 40, 41, 60, 4 }
Expected Answer is : 4
Actual Answer is : 3
There is minor bug in the code which is causing incorrect output for the cases mentioned above. Actually you don't need to reset head to i when condition fails.
Here is c# code after fixing the bug
public static void getMaxLength(int[] arr) {
int len = arr.Length;
int maxCount = 0;
for(int i=0;i<len;i++) {
int head = i; int tail = len-1;
int max = 0; // Max value of smaller sub-array
int min = int.MaxValue; // Min value of larger sub-array
int currentCount = 0; // Max length sub-array for elements starting at index i
int startMax = -1; // 1 = head represents larger sub-array ; 2 = tail represents larger sub-array
while(tail > head) {
if(startMax == -1)
{
startMax = arr[head] > arr[tail] ? 1 : 0;
max = (startMax == 1) ? Math.Max(max, arr[tail]) : Math.Max(max, arr[head]);
min = (startMax == 1) ? Math.Min(min, arr[head]) : Math.Min(min, arr[tail]);
head++;
tail--;
currentCount++;
maxCount = (currentCount >= maxCount) ? currentCount : maxCount;
continue;
}
else {
if((startMax == 1) && ((arr[head] < arr[tail]) || (arr[head] < max) || (arr[tail] > min))) {
startMax = -1;
max = 0;
min = int.MaxValue;
//head = i;
currentCount = 0;
continue;
}
else if((startMax == 0) && ((arr[head] > arr[tail]) || (arr[head] > min) || (arr[tail] < max))) {
startMax = -1;
max = 0;
min = int.MaxValue;
//head = i;
currentCount = 0;
continue;
}
}
max = (startMax == 1) ? Math.Max(max, arr[tail]) : Math.Max(max, arr[head]);
min = (startMax == 1) ? Math.Min(min, arr[head]) : Math.Min(min, arr[tail]);
head++;
tail--;
currentCount++;
maxCount = (currentCount >= maxCount) ? currentCount : maxCount;
}
}
Console.WriteLine("Max Length = " + maxCount);
}
public static void Main(string[] args)
{
getMaxLength(new int[] { 20, 5, 7, 2, 11, 55, 9, 26, 48, 22, 12 }); // Expected 4
getMaxLength(new int[] { 20, 5, 7, 2, 11, 55, 9, 26, 48, 22, 10 }); // Expeced 3
getMaxLength(new int[] { 10, 5, 100, 2, 70, 3, 60, 1, 99, 4, 66 }); // expected 1
getMaxLength(new int[] { 6, 50, 7, 35, 1, 2, 3, 8, 45, 5, 30, 40, 41, 60, 4 }); // Expcted 4
}
Say k = size of each sequence. Check all subsequences length k from k = 1 to n/2. Keep track of the min/max of subsequences. If subsequences are non intersecting and the max of one is smaller than a min of the other, you've found your answer. This is expected to be an O(n^3) algorithm
We can use DP to solve this problem in O(n^2)
void longestSubArray(int A[], int n)
{
int *dp[2]; for (int i = 0; i < 2; ++i) dp[i] = new int[n];
int len = 0, s1 = 0, s2 = 0;
for (int i = n - 1; i >= 0; --i)
{
dp[i & 1][i] = 0; dp[i & 1][n - 1] = 1;
for (int j = n - 2; j > i; --j)
{
int tmp = (A[i] > A[j]) == (A[i + 1] > A[j + 1]) ? dp[(i + 1) & 1][j + 1] + 1 : 1;
if (tmp > j - i) tmp = j - i;
if (tmp > len)
{
len = tmp; s1 = i; s2 = j;
}
dp[i & 1][j] = tmp;
}
}
if (len == 0)
{
cout << "no answer!" << endl;
}
cout << "first subarray: "; for (int i = s1; i < s1 + len; ++i) cout << A[i] << " "; cout << endl;
cout << "second subarray: "; for (int i = s2; i < s2 + len; ++i) cout << A[i] << " "; cout << endl;
}
I honestly don't know what you're doing there. Care to elaborate?
In any case, whatever it is, it is wrong. With this input it already fails: {1,2,5,3,7,4,9,8}.
nope, for this array: [7,6,5,4,9,11,3,2,8]
it returns
first subarray: 4 9 11
second subarray: 3 2 8
which is not correct
Sorting will change the order of arrary element, and the problem will reduce to max sub arraylegnth = arraylegnth/2 which is straightforward.Better to check with interviewer before hand.
Here my logic by brute force first:
1. MaxSubArrayLength = InPutArray.Length /2
2. While MaxSubarrayLength>=2
3. Create sub arrays of length MaxSubarrayLength . Incase of inputArray of length 8, we will get 2 subarrays of length 4 each. If these array comparison doesnt gives our result we decrease MaxSubArrayLength by 1 (untill we reach 2).
4. In our case array of length 8 with sub array of length 3 will give us 6 subarrays which we compare in pairs to check if we get desired result. If we get our desire result we stop.
thats max sub array length ans sub array
Here's an adaptation of the LCS (longest common substring) algorithm. N^2.
static void FindSubarrays(int[] values, out int first, out int second, out int size)
{
var acc = new int[values.Length + 1, values.Length + 1];
size = 0;
first = -1;
second = -1;
for (int i = 0; i <= values.Length; i++)
{
for (int j = 0; j <= values.Length; j++)
{
if (i == 0 || j == 0 || values[i-1] >= values[j-1])
acc[i, j] = 0;
else
{
int maxDistance = MaxDistance(i, j);
acc[i, j] = Math.Min(acc[i - 1, j - 1] + 1, maxDistance);
if (size < acc[i, j])
{
size = acc[i, j];
first = i - size;
second = j - size;
}
}
}
}
}
static int MaxDistance(int i, int j)
{
int first = Math.Min(i, j);
int distance = Math.Abs(i - j);
return Math.Min(first, distance);
}
The question also says that all numbers are unique. That may be a key for a simpler solution, which I do not see yet.
Below code is perfect. we must reset the head to i but at the same time we need to take care of the tail. a few manipulations to the code written by Riku will give us the result. Anyways credit goes to riku.
public class ss {
public static void getMaxLength(int[] arr) { int leng = arr.length;
int maxCount = 0;
for(int i=0;i<leng;i++) {
int len=arr.length;
int head = i; int tail = len-1;
int max = 0; // Max value of smaller sub-array
int min = Integer.MAX_VALUE; // Min value of larger sub-array
int currentCount = 0; // Max length sub-array for elements starting at index i
int startMax = -1; // 1 = head represents larger sub-array ; 2 = tail represents larger sub-array
while(tail > head) {
if(startMax == -1)
startMax = arr[head] > arr[tail] ? 1 : 0;
else {
if((startMax == 1) && ((arr[head] < arr[tail]) || (arr[head] < max) || (arr[tail] > min))) {
startMax = -1; max = 0; min = Integer.MAX_VALUE; head = i; len--;tail=len;
currentCount = 0;
continue;
}
else if((startMax == 0) && ((arr[head] > arr[tail]) || (arr[head] > min) || (arr[tail] < max))) {
startMax = -1; max = 0; min = Integer.MAX_VALUE; head = i; len--;tail=len;
currentCount = 0; continue;
}
}
max = (startMax == 1) ? Math.max(max, arr[tail]) : Math.max(max, arr[head]);
min = (startMax == 1) ? Math.min(min, arr[head]) : Math.min(min, arr[tail]);
head++; tail--; currentCount++;
maxCount = (currentCount >= maxCount) ? currentCount : maxCount;
}
}
System.out.println("Max Length = " + maxCount);
}
public static void main(String[] args) {
getMaxLength(new int[] {6, 50, 7, 35, 1, 2, 3, 8, 45, 5, 30, 40, 41, 60, 4 }); // Expected 4
}
}
Below Solution having - O(n^4) complexity
-------------------------------------------------------------------------------------------------
void printMaxContiguousSubArrays(int[] arr) {
// max sequence will be equal to the size of the input array/2
int maxSeq = arr.length / 2;
int k = maxSeq;
// k>1 because we do not want to have sublists of array size 1 as output
while (k > 1) {
// divide into subarrays of size k
List<List<Integer>> subArrays = divideIntoSubArrays(arr, k);
// compare contents of sublists to find the legitimate combination
for (int i = 0; i < subArrays.size(); i++) {
List<Integer> tempSubList1 = subArrays.get(i);
// System.out.println(subList);
for (int j = i + 1; j < subArrays.size(); j++) {
List<Integer> tempSubList2 = subArrays.get(j);
// sort the sublists to compare. sorted sublists will be stored in temp sublists
List<Integer> tempSubListSorted1 = sort(tempSubList1);
List<Integer> tempSubListSorted2 = sort(tempSubList2);
if ((tempSubListSorted1.get(0) > tempSubListSorted2.get(0) && tempSubListSorted1.get(0) > tempSubListSorted2.get(tempSubListSorted2.size() - 1)
&& tempSubListSorted1.get(tempSubListSorted1.size() - 1) > tempSubListSorted2.get(0) && tempSubListSorted1.get(tempSubListSorted1.size() - 1) > tempSubListSorted2.get(tempSubListSorted2.size() - 1))
|| (tempSubListSorted1.get(0) < tempSubListSorted2.get(0) && tempSubListSorted1.get(0) < tempSubListSorted2.get(tempSubListSorted2.size() - 1)
&& tempSubListSorted1.get(tempSubListSorted1.size() - 1) < tempSubListSorted2.get(0) && tempSubListSorted1.get(tempSubListSorted1.size() - 1) < tempSubListSorted2.get(tempSubListSorted2.size() - 1))) {
System.out.println("Maximum contiguous sequence sub arrays are: " + tempSubList1 + " and " + tempSubList2);
return;
}
}
}
k--;
}
System.out.println("No contiguous subarrays found meeting the required conditions");
}
// method to sort the input list of integers
List<Integer> sort(List<Integer> lst) {
List<Integer> tempLst = new ArrayList<Integer>();
for (Integer i : lst) {
tempLst.add(i);
}
Collections.sort(tempLst);
return tempLst;
}
// divide the array into contiguous blocks arrays of size k
List<List<Integer>> divideIntoSubArrays(int[] arr, int k) {
List<List<Integer>> subArrays = new ArrayList<List<Integer>>();
List<Integer> subList = null;
int j = 0;
for (int l = 0; l < arr.length; l++) {
int i = l;
while (i < arr.length) {
if (j == k)
j = 0;
if (j == 0) {
subList = new ArrayList<Integer>();
subArrays.add(subList);
}
subList.add(arr[i]);
j++;
i++;
}
}
return subArrays;
}
Below Solution having - O(n^4) complexity
-------------------------------------------------------------------------------------------------
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class PrintContiguousSubArrays {
public static void main(String[] args) {
int[] arr = { 6, 5, 4, 1, 3, 7 };
printMaxContiguousSubArrays(arr);
}
static void printMaxContiguousSubArrays(int[] arr) {
// max sequence will be equal to the size of the input array/2
int maxSeq = arr.length / 2;
int k = maxSeq;
// k>1 because we do not want to have sublists of array size 1 as output
while (k > 1) {
// divide into subarrays of size k
List<List<Integer>> subArrays = divideIntoSubArrays(arr, k);
// compare contents of sublists to find the legitimate combination
for (int i = 0; i < subArrays.size(); i++) {
List<Integer> tempSubList1 = subArrays.get(i);
// System.out.println(subList);
for (int j = i + 1; j < subArrays.size(); j++) {
List<Integer> tempSubList2 = subArrays.get(j);
// sort the sublists to compare. sorted sublists will be stored in temp sublists
List<Integer> tempSubListSorted1 = sort(tempSubList1);
List<Integer> tempSubListSorted2 = sort(tempSubList2);
if ((tempSubListSorted1.get(0) > tempSubListSorted2.get(0) && tempSubListSorted1.get(0) > tempSubListSorted2.get(tempSubListSorted2.size() - 1)
&& tempSubListSorted1.get(tempSubListSorted1.size() - 1) > tempSubListSorted2.get(0) && tempSubListSorted1.get(tempSubListSorted1.size() - 1) > tempSubListSorted2.get(tempSubListSorted2.size() - 1))
|| (tempSubListSorted1.get(0) < tempSubListSorted2.get(0) && tempSubListSorted1.get(0) < tempSubListSorted2.get(tempSubListSorted2.size() - 1)
&& tempSubListSorted1.get(tempSubListSorted1.size() - 1) < tempSubListSorted2.get(0) && tempSubListSorted1.get(tempSubListSorted1.size() - 1) < tempSubListSorted2.get(tempSubListSorted2.size() - 1))) {
System.out.println("Maximum contiguous sequence sub arrays are: " + tempSubList1 + " and " + tempSubList2);
return;
}
}
}
k--;
}
System.out.println("No contiguous subarrays found meeting the required conditions");
}
static List<Integer> sort(List<Integer> lst) {
List<Integer> tempLst = new ArrayList<Integer>();
for (Integer i : lst) {
tempLst.add(i);
}
Collections.sort(tempLst);
return tempLst;
}
// divide the array into contiguous blocks arrays of size k
static private List<List<Integer>> divideIntoSubArrays(int[] arr, int k) {
List<List<Integer>> subArrays = new ArrayList<List<Integer>>();
List<Integer> subList = null;
int j = 0;
for (int l = 0; l < arr.length; l++) {
int i = l;
while (i < arr.length) {
if (j == k)
j = 0;
if (j == 0) {
subList = new ArrayList<Integer>();
subArrays.add(subList);
}
subList.add(arr[i]);
j++;
i++;
}
}
return subArrays;
}
}
Here is the techinque, took some time to figure it out,
We need some space to figure out this problem, the space required for this problem is n*n, because there will be n*n many intervals, we need this space to save the min/max of an internal and help in figure out the min and max of its near by intervals in o(1) time.
Here is the algorithm
n <- size of the array A
define M(n,n) as two value matrix storing both min and max, where M(i,j) repersents min and max between the array i and j, This will a symmetric matrix(M(i,j) = M(j,i)
set M(i,j) = (min = infinity, max = -infinity)
For k = 2 to n/2 // as one size sub is always a solution for this problem
for j = 1 to n-2k // assuming array from A[1 to n]
if M(j,j+k) is not defined, define it
for i = j+k+1 to n-k
if M(i,i+k) is not defined, define it
if M(j,j+k) and M(i,i+k) satisfy the condition,
save k and indexes to return the answer at the end, we will overwrite the old values of k is higher
end
end
end
Here is the condition about which i am talking about
Condition_check((Min1,Max1),(Min2,Max2))
if Max1 < Min2 or Min1 > Max2 then return true else return false
Here is how we define the vales of M
Set_MValues(A,M,i,j)
If Defined(M(i,j-1)
Then Min(M(i,j) = Min(A[j], Min(M(i,j-1)) and Max(M(i,j) = Max(A[j], Max(M(i,j-1))
If Defined(M(i-1,j)
Then Min(M(i,j) = Min(A[i], Min(M(i-1,j)) and Max(M(i,j) = Max(A[i], Max(M(i-1,j))
else figure out min and max between A(i...j].
Complexity
Time : O(n*n*n)
Space : O(n*n)
import java.util.LinkedList;
import java.util.Queue;
public class maxLenSubArrays {
public static void main(String[] args){
int[] nums = { 6, 50, 7, 35, 1, 2, 3, 8, 45, 5, 30, 40, 41, 60, 4};
int n = nums.length;
int[][] mins = buildMins(nums);
int[][] maxs = buildMaxs(nums);
LinkedList<LinkedList<Integer>[]> output = getComb(nums, mins, maxs);
for(LinkedList<Integer>[] res: output){
LinkedList<Integer> first = res[0];
LinkedList<Integer> second = res[1];
System.out.print("(");
for(int i: first) System.out.print(i + " ");
System.out.print(") - (");
for(int i: second) System.out.print(i + " ");
System.out.println(")");
}
}
public static int[][] buildMins(int[] nums){
int n = nums.length;
int size = n;
int[][] mins = new int[n][n];
while(size > 0){
minQueue minQ = new minQueue(size);
for(int i = 0; i < n; i++ ){
minQ.add(nums[i]);
if(i >= size -1) mins[i- size + 1][i] = minQ.getMin();
}
size--;
}
return mins;
}
public static int[][] buildMaxs(int[] nums){
int n = nums.length;
int size = n;
int[][] maxs = new int[n][n];
while(size > 1){
maxQueue maxQ = new maxQueue(size);
for(int i = 0; i < n; i++ ){
maxQ.add(nums[i]);
if(i >= size - 1) maxs[i-size + 1][i] = maxQ.getMax();
}
size--;
}
return maxs;
}
public static LinkedList<LinkedList<Integer>[]> getComb(int[] nums, int[][] mins, int[][] maxs){
LinkedList<LinkedList<Integer>[]> output =(LinkedList<LinkedList<Integer>[]>) new LinkedList();
int n = nums.length;
int size = n / 2;
int twosize = size * 2;
boolean found = false;
//complexity = size * i / size * i / size, hence n^2
while(size > 1 && !found){
for(int i = 0; i < n - twosize + 1; i++){
int firstmin = mins[i][i+size-1];
int firstmax = maxs[i][i+size-1];
for(int j = i + size; j < n - size + 1; j++){
int secondmin = mins[j][j+size-1];
int secondmax = mins[j][j+size-1];
if(firstmax < secondmin || firstmin > secondmax) {
found = true;
output.add(buildArr(nums, i, j, size));
}
}
}
size--;
}
return output;
}
private static LinkedList[] buildArr(int[] nums, int i, int j, int size){
LinkedList[] res = (LinkedList<Integer>[]) new LinkedList[2];
LinkedList<Integer> first = new LinkedList<>();
for(int k = i; k < i + size ; k++) first.add(nums[k]);
res[0] = first;
LinkedList<Integer> second = new LinkedList<>();
for(int k = j; k < j + size ; k++) second.add(nums[k]);
res[1] = second;
return res;
}
static class maxQueue{
Queue<Integer> mainq = new LinkedList<>();
LinkedList<Integer> maxq = new LinkedList<>();
int size = 0;
public maxQueue(int size){
this.size = size;
}
public void add(int val){
if(mainq.size() == size) remove();
while(!maxq.isEmpty() && maxq.get(maxq.size() - 1) < val) maxq.remove(maxq.size() - 1);
maxq.add(val);
mainq.add(val);
}
public void remove(){
if(mainq.isEmpty()) return;
int val = mainq.peek();
if(!maxq.isEmpty() && maxq.get(0) == val) maxq.remove(0);
mainq.remove();
}
public int getMax(){
if(maxq.isEmpty()) return Integer.MIN_VALUE;
return maxq.get(0);
}
public int size(){
return mainq.size();
}
}
static class minQueue{
Queue<Integer> mainq = new LinkedList<>();
LinkedList<Integer> minq = new LinkedList<>();
int size = 0;
public minQueue(int size){
this.size = size;
}
public void add(int val){
if(mainq.size() == size) remove();
while(!minq.isEmpty() && minq.get(minq.size() - 1) > val) minq.remove(minq.size() - 1);
minq.add(val);
mainq.add(val);
}
public void remove(){
if(mainq.isEmpty()) return;
int val = mainq.peek();
if(!minq.isEmpty() && minq.get(0) == val) minq.remove(0);
mainq.remove();
}
public int getMin(){
if(minq.isEmpty()) return Integer.MIN_VALUE;
return minq.get(0);
}
public int size(){
return mainq.size();
}
}
}
import java.util.LinkedList;
import java.util.Queue;
public class maxLenSubArrays {
public static void main(String[] args){
int[] nums = { 6, 50, 7, 35, 1, 2, 3, 8, 45, 5, 30, 40, 41, 60, 4};
int n = nums.length;
int[][] mins = buildMins(nums);
int[][] maxs = buildMaxs(nums);
LinkedList<LinkedList<Integer>[]> output = getComb(nums, mins, maxs);
for(LinkedList<Integer>[] res: output){
LinkedList<Integer> first = res[0];
LinkedList<Integer> second = res[1];
System.out.print("(");
for(int i: first) System.out.print(i + " ");
System.out.print(") - (");
for(int i: second) System.out.print(i + " ");
System.out.println(")");
}
}
public static int[][] buildMins(int[] nums){
int n = nums.length;
int size = n;
int[][] mins = new int[n][n];
while(size > 0){
minQueue minQ = new minQueue(size);
for(int i = 0; i < n; i++ ){
minQ.add(nums[i]);
if(i >= size -1) mins[i- size + 1][i] = minQ.getMin();
}
size--;
}
return mins;
}
public static int[][] buildMaxs(int[] nums){
int n = nums.length;
int size = n;
int[][] maxs = new int[n][n];
while(size > 1){
maxQueue maxQ = new maxQueue(size);
for(int i = 0; i < n; i++ ){
maxQ.add(nums[i]);
if(i >= size - 1) maxs[i-size + 1][i] = maxQ.getMax();
}
size--;
}
return maxs;
}
public static LinkedList<LinkedList<Integer>[]> getComb(int[] nums, int[][] mins, int[][] maxs){
LinkedList<LinkedList<Integer>[]> output =(LinkedList<LinkedList<Integer>[]>) new LinkedList();
int n = nums.length;
int size = n / 2;
int twosize = size * 2;
boolean found = false;
//complexity = size * i / size * i / size, hence n^2
while(size > 1 && !found){
for(int i = 0; i < n - twosize + 1; i++){
int firstmin = mins[i][i+size-1];
int firstmax = maxs[i][i+size-1];
for(int j = i + size; j < n - size + 1; j++){
int secondmin = mins[j][j+size-1];
int secondmax = mins[j][j+size-1];
if(firstmax < secondmin || firstmin > secondmax) {
found = true;
output.add(buildArr(nums, i, j, size));
}
}
}
size--;
}
return output;
}
private static LinkedList[] buildArr(int[] nums, int i, int j, int size){
LinkedList[] res = (LinkedList<Integer>[]) new LinkedList[2];
LinkedList<Integer> first = new LinkedList<>();
for(int k = i; k < i + size ; k++) first.add(nums[k]);
res[0] = first;
LinkedList<Integer> second = new LinkedList<>();
for(int k = j; k < j + size ; k++) second.add(nums[k]);
res[1] = second;
return res;
}
static class maxQueue{
Queue<Integer> mainq = new LinkedList<>();
LinkedList<Integer> maxq = new LinkedList<>();
int size = 0;
public maxQueue(int size){
this.size = size;
}
public void add(int val){
if(mainq.size() == size) remove();
while(!maxq.isEmpty() && maxq.get(maxq.size() - 1) < val) maxq.remove(maxq.size() - 1);
maxq.add(val);
mainq.add(val);
}
public void remove(){
if(mainq.isEmpty()) return;
int val = mainq.peek();
if(!maxq.isEmpty() && maxq.get(0) == val) maxq.remove(0);
mainq.remove();
}
public int getMax(){
if(maxq.isEmpty()) return Integer.MIN_VALUE;
return maxq.get(0);
}
public int size(){
return mainq.size();
}
}
static class minQueue{
Queue<Integer> mainq = new LinkedList<>();
LinkedList<Integer> minq = new LinkedList<>();
int size = 0;
public minQueue(int size){
this.size = size;
}
public void add(int val){
if(mainq.size() == size) remove();
while(!minq.isEmpty() && minq.get(minq.size() - 1) > val) minq.remove(minq.size() - 1);
minq.add(val);
mainq.add(val);
}
public void remove(){
if(mainq.isEmpty()) return;
int val = mainq.peek();
if(!minq.isEmpty() && minq.get(0) == val) minq.remove(0);
mainq.remove();
}
public int getMin(){
if(minq.isEmpty()) return Integer.MIN_VALUE;
return minq.get(0);
}
public int size(){
return mainq.size();
}
}
}
time: O(N^2 * log(N)), space O(N)
for each possible length L of a continuous sub-array, find all possible N-L+1 sub-arrays, and calculate the min/max of values in each sub-array. This can be done in N.
Now the question is checking if there exists two non-overlapped intervals: This can be done in n*log(n) after sorting the intervals by their min values.
I think we are going to have an O(n^4) algorithm.
First how many sub arrays could there be in a range of n numbers
It is not counted as a group if there is only 1 element in it.
For 2 elements you get n-1 groups
For 3 you get n-2
And so on
(n-1)+(n-2)+(n-3)…..(1)
(n^2 + n)/2 – n
(n^2 –n)/2
Now lets say we have numbers from 1 to k inclusive
For a given set i to j (where i is at least one smaller then j ) inclusive we can match with any set before or after it
We won’t count the sets before it so we don’t double count
It boggles the mind but it looks pretty O(n^4) to me.
I don’t recall how to compute the series.
But the code will look like 4 nested loops I think hopefully not 6
This is an O(n^2) solution, although it is very clumsy. Here, i have just iterated through all the elements as starting position of 1 sub-array, and traversed from the end to find the max length under the given conditions.
- riku May 23, 2015public void getMaxLength(int[] arr) { int len = arr.length; int maxCount = 0; for(int i=0;i<len;i++) { int head = i; int tail = len-1; int max = 0; // Max value of smaller sub-array int min = Integer.MAX_VALUE; // Min value of larger sub-array int currentCount = 0; // Max length sub-array for elements starting at index i int startMax = -1; // 1 = head represents larger sub-array ; 2 = tail represents larger sub-array while(tail > head) { if(startMax == -1) startMax = arr[head] > arr[tail] ? 1 : 0; else { if((startMax == 1) && ((arr[head] < arr[tail]) || (arr[head] < max) || (arr[tail] > min))) { startMax = -1; max = 0; min = Integer.MAX_VALUE; head = i; currentCount = 0; continue; } else if((startMax == 0) && ((arr[head] > arr[tail]) || (arr[head] > min) || (arr[tail] < max))) { startMax = -1; max = 0; min = Integer.MAX_VALUE; head = i; currentCount = 0; continue; } } max = (startMax == 1) ? Math.max(max, arr[tail]) : Math.max(max, arr[head]); min = (startMax == 1) ? Math.min(min, arr[head]) : Math.min(min, arr[tail]); head++; tail--; currentCount++; maxCount = (currentCount >= maxCount) ? currentCount : maxCount; } } System.out.println("Max Length = " + maxCount); }