/*
Problem: Maximum Non-Overlapping Increasing Subsequences (UCF Local 2017)
Author: Shahidul Islam (Sumon)
*/
#include
#include
#include
#define ARRAY_SZ 101
int array[ARRAY_SZ];
int lisArray[ARRAY_SZ];
int pairwiseLIS[ARRAY_SZ][ARRAY_SZ];
int matrix[ARRAY_SZ][ARRAY_SZ][ARRAY_SZ];
int lis(int *array, int count);
void parenthesize(int array[], int count);
int main()
{
freopen("mnois.in", "r", stdin);
int i, j, n, m, optParenthesis;
//Input and Output
scanf("%d", n);
for(i = 1; i 1
for(k = 0; k = 0; i--)
{
for (j = i + 1; j = k + 1)
matrix[k][i][j] = pairwiseLIS[i][j];
else
matrix[k][i][j] = 0;
for (l = i; l matrix[k][i][j])
matrix[k][i][j] = elements;
}
}
}
}
}
//Calculate LIS length from count items in array
int lis(int *array, int count)
{
int i, j, len = 0, lo, hi, mid;
for(i = 0; i < count; i++)
{
lo = -1;
hi = len;
while(lo < hi - 1)
{
mid = (lo + hi) / 2;
if(lisArray[mid] < array[i])
lo = mid;
else
hi = mid;
}
lisArray[hi] = array[i];
if(hi == len)
len++;
}
return len;
}