Find the length of the longest increasing subsequence using only one auxiliary recursion function


I need to find the length of the longest monotonically increasing subsequence using only a single recursion function. For example given an arr={45 1 21 3 33 6 53 9 18} it need to give back 5. I have started to write the code but i'm stuck, and i don't know how to find out which of the calls gives the maximum length.

The function longestSet is my auxiliary function i can use any variables i want but it have to be called from the function max_set.

void question3(int question) { int *arr, size; printf("enter the array size\n"); scanf("%d", &size); arr=(int*)malloc(size*sizeof(int)); fillArr(arr, size-1); max_set(arr, size); free(arr); } void max_set(int arr[], int size) { int i=0, finelmax=0, count=0,longrising; longrising=longestSet(arr,size,i,finelmax,count); printf("the length of the longest risind set is: %d", longrising); } int longestSet(int arr[], int size, int i, int finelmax, int count) { if(i==size) return count; if(arr[i]>=finelmax) { finelmax=arr[i]; return longestSet(arr,size,i+1,finelmax,count+1); } return longestSet(arr,size,i+1,finelmax,count); }


Something like this:

int longestSet(int arr[], int size, int i, int finelmax, int count) { if(i==size) return count; int length1 = longestSet(arr, size, i + 1, finelmax, count); if(arr[i] > finelmax) { int length2 = longestSet(arr, size, i + 1, arr[i], count + 1); if(length2 > length1) length1 = length2; } return length1; }

What this basically does is at each point compare if it would be better to include the current number or skip it. Also will be pretty slow - you can for example add memoization to it to improve, but I'm guessing that's not part of the homework?


I'm giving here the full code with a single recursion function you asked. Unfortunately it's in java but your purpose would be solved as the function used for recursion is almost same.

import java.util.StringTokenizer; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; class longestSubSequence{ public static void main (String [] args)throws IOException{ new longestSubSequence().run(); } int max = -1; int index = 1; int [] array; private void run() throws IOException{ array = new int [50]; BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // Input your array StringTokenizer st = new StringTokenizer (br.readLine()); array[0] = -1; while (st.hasMoreTokens()){ array[index++] = Integer.parseInt(st.nextToken()); } index--; dfs (0, 0); System.out.println(max);// Prints the maximum length } private void dfs (int curr, int length){ if (length > max )max = length; if (curr >= index) return ; for (int I=curr+1;I <= index; I++){ if (array[I] >= array[curr]){ dfs (I, length+1); } } } }


  • Can we reuse allocated memory
  • Calculating Digital Root, is there a better way?
  • Salted sha512 in C, cannot synchronise with Symfony2's FOSUserBundle
  • Getting segmentation fault while using malloc
  • Making a switch statement in C with an array?
  • How to delete a newline using \\b
  • How to work with AMMediaType for video filters
  • How to unpack 32bit integer packed in a QByteArray?
  • allocating memory to an array of string
  • Redshift Querying: error xx000 disk full redshift
  • DIV instruction jumping to random location?
  • Convert Type Decimal to Hex (string) in .NET 3.5
  • Appending Character to Character Array In C
  • PHP CURL timing out but CLI CURL works
  • Declaring variable dynamically in VB.net
  • CakePHP 2.0.4 - findBy magic methods with conditions
  • Jackson Parser: ignore deserializing for type mismatch
  • why overloaded new operator is calling constructor even I am using malloc inside overloading functio
  • Initializer list vs. initialization method
  • Xamarin Forms - UWP Fonts
  • Android screen density dpi vs ppi
  • C# - Is there a limit to the size of an httpWebRequest stream?
  • Why is the size of this struct 32?
  • JavaScriptCore crash on iOS9
  • Date difference with leap year
  • DirectX11 ClearRenderTargetViewback with transparent buffer?
  • Arrow is showed instead of the material design version hamburger icon. Why doesn't syncState in
  • Can I have the cursor start on a particular column by default in jqgrid's edit mode?
  • Change an a tag attribute in JavaScript based on screen width
  • Rearranging Cells in UITableView Bug & Saving Changes
  • Circular dependency while pushing http interceptor
  • Arrays break string types in Julia
  • Linker errors when using intrinsic function via function pointer
  • Benchmarking RAM performance - UWP and C#
  • How get height of the a view with gone visibility and height defined as wrap_content in xml?
  • Angular 2 constructor injection vs direct access
  • FormattedException instead of throw new Exception(string.Format(…)) in .NET
  • IndexOutOfRangeException on multidimensional array despite using GetLength check
  • Sorting a 2D array using the second column C++
  • java string with new operator and a literal