fork download
copy 
  1. //hold the LIS values for memoization
  2. int *lisTable = NULL;
  3. //hold the indexes stored as linked pointer , given the first index idx first value is arr[idx] , next value will be linked at
  4. //lisIndex[idx] = idx1 , next value is arr[idx1] , the next is at index lisIndex[idx1] .. so on untill -1 is returned by lisIndex[] to mark end
  5. int *lisIndex = NULL;
  6.  
  7. void initLisTable (int n)
  8. {
  9. 	int i;
  10.  
  11. 	lisIndex = (int*) malloc (sizeof (int)*(n));
  12. 	lisTable = (int*) malloc (sizeof (int)*(n));
  13. 	lisTable[0] = 1;//holds the maximum length
  14. //since lis(0) is of length one with element arr[0]s
  15. 	lisIndex[0] = -1;
  16.  
  17. 	for (i = 1 ; i<n ; i++)
  18. 	{
  19. 		lisTable[i] = -1;
  20. 		lisIndex[i] = -1;
  21. 	}
  22. }
  23.  
  24. void printLisDetail (int arr[],int maxLen ,int n)
  25. {
  26. 	int i;
  27.  
  28. 	//calculate the idx of lis stored in listable which corresponds to max in length
  29. 	for ( i = 0; i < n ; i++)
  30. 	{
  31. 		if (lisTable[i] == maxLen)
  32. 			break;
  33. 	}
  34. 	printf ("Lis elements\n");
  35.  
  36. 	//start from this lis and print all the elements of this lis
  37. 	while (i != -1)
  38. 	{
  39. 		printf ("%d   ",arr[i]);
  40. 		//get the next index of this lis from lisIndex table which maps to arr[]
  41. 		i = lisIndex[i];
  42. 	}
  43. 	printf ("\n");
  44. }
  45.  
  46. int lis_DP (int arr[], int n, int * max)
  47. {
  48. 	int i, ret, max_val = -1 , idx  = -1;
  49.  
  50. 	//if value exists in looktable return from there so that recursion is minimized
  51. 	if (lisTable[n] >= 0)
  52. 		return lisTable[n];
  53.  
  54. 	for (i = 0 ; i < n ; i++)
  55. 	{
  56. 		//calculate LIS for i = 0 to i n , and set the max length of LIS in max
  57. 		// lis(i) = 1+max(lis(j))  j is -> 0 <= j <= i and for which arr[i] > arr[j] is true or 1 if no such j exist	= 1
  58.  
  59. 		ret = lis_DP (arr, i,max);
  60. 		//if lis of this elment is > than the previous element then update overall max
  61. 		if (ret > max_val)
  62. 		{
  63. 			*max = ret;
  64. 			//to calculate lis(n) if this satisfy second condition of equation above
  65. 			//save it to max_val and idx for further processing and further checking with other less than n elements
  66. 			if (arr[i] <= arr[n])
  67. 			{
  68. 				max_val = ret;
  69. 				idx = i;
  70. 			}
  71. 		}
  72. 	}
  73.  
  74. 	//if second condition of above holds true
  75. 	if (max_val == -1)
  76. 	{
  77. 		lisTable[n] = 1;
  78. 		// one element lis with only element = n , so index points to end
  79. 		lisIndex[n] = -1;
  80. 	}
  81. 	else
  82. 	{
  83. 		lisTable[n] = 1 + max_val;
  84. 		//update the index of the lis(n) to max lis calculated , this recursivly points to the elements in arr[] using lisIndex[]
  85. 		lisIndex[n] = idx;
  86. 	}
  87. 	return lisTable[n];
  88. }
  89.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.c:2:17: error: ‘NULL’ undeclared here (not in a function)
 int *lisTable = NULL;
                 ^
prog.c: In function ‘initLisTable’:
prog.c:11:2: warning: implicit declaration of function ‘malloc’ [-Wimplicit-function-declaration]
  lisIndex = (int*) malloc (sizeof (int)*(n));
  ^
prog.c:11:20: warning: incompatible implicit declaration of built-in function ‘malloc’ [enabled by default]
  lisIndex = (int*) malloc (sizeof (int)*(n));
                    ^
prog.c: In function ‘printLisDetail’:
prog.c:34:2: warning: implicit declaration of function ‘printf’ [-Wimplicit-function-declaration]
  printf ("Lis elements\n");
  ^
prog.c:34:2: warning: incompatible implicit declaration of built-in function ‘printf’ [enabled by default]
stdout
copy 
Standard output is empty
https://ideone.com/1f2E9I
language:
C (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!