CareerCup

public static void LIS_bottom_up(int[] array,int length)
{
int[] array2 = {4,6,7,3,9,5,7,0,-1,10};
int max = Integer.MIN_VALUE;
int[] tmparray_increase = new int[length+1];
int[] tmparray_decrease = new int[length+1];
for(int i=0;i<=length;i++)
{
tmparray_increase[i]=1;
tmparray_decrease[i]=1;
for(int j=0;j<=i;j++)
{
if(array[j]<array[i])
{
tmparray_increase[i]=Math.max(tmparray_increase[i], tmparray_decrease[j]+1);
}
if(array[j]>array[i])
{
tmparray_decrease[i]=Math.max(tmparray_decrease[i], tmparray_increase[j]+1);
}
}
max = Math.max(max, Math.max(tmparray_increase[i],tmparray_decrease[i]));
}
for(int i=0;i<=length;i++)
{
System.out.print(tmparray_increase[i]+"\t");
}
System.out.print("\n");
for(int i=0;i<=length;i++)
{
System.out.print(tmparray_decrease[i]+"\t");
}
System.out.println("Max = "+max);
}

Keep merging data from both list , insert first interval with lesser start

Arr1 = [3-11, 17-25, 58-73];
Arr2 = [6-18, 40-47];

Arr3 = 3-11,

Arr1 = 17-25,58-73
Arr2 = 6-18,40-47

when inserting next interval check if curlow <= A3.high && curhigh >A3.high, if so update A3.high, else add (curlow-curhigh) to list

A3 = 3,18
Arr1 = 17-25,58-73
Arr2 = 40-47

A3 = 3,25
Arr1 = 58-73
Arr2 = 40-47

A3 = 3,25, 40-47, 58-73