仅使用一个辅助递归函数查找最长增长子序列的长度

我需要仅使用一个递归函数找到最长单调递增子序列的长度。 例如，给定一个arr={45 1 21 3 33 6 53 9 18}它需要回馈5.我已经开始编写代码但我被卡住了，我不知道如何找出哪个调用给出了最大长度。

函数longestSet是我的辅助函数我可以使用我想要的任何变量，但它必须从函数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); } 

Answer 1

像这样的东西：

 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; } 

这基本上做的是在每个点比较是否更好地包括当前数字或跳过它。 也会很慢 – 例如你可以添加memoization来改进，但我猜这不是作业的一部分？

Answer 2

我在这里给你完整的代码，你会问一个递归函数。 不幸的是它在java中，但你的目的将被解决，因为用于递归的函数几乎相同。

 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); } } } }