使用递归和无循环查找数组中最长的升序子系列的长度
我已经被困了好几个小时试图想象我怎样才能编写一个获取整数和整数数组的函数，并使用递归找到数组中最长的升序子系列的长度而根本没有循环。 我只允许使用另外一个递归函数，例如，对于以下数组：{45,1,21,3,3,6,53,9,18} outpot应该是5，因为最长的子系列是{ 1,3,6,9,18}。 所以，基本上，一个获取数组及其大小的函数，需要打印最长子系列的长度，根本不使用循环，没有全局/静态类型，它可能使用另一个“帮助”递归函数，那就是它。 这几乎就是我提出的所有内容，而且它一团糟，效果不佳。 我正在尝试扫描数组，同时我知道当前正在查看的索引，与当前比较的索引，以及从中启动当前子系列的originla索引。 我试图扫描arrays，同时知道应该比较的索引，但我卡住了，这是我得到的，我真的很感激任何提示和建议。 谢谢。
void max_set(int arr[], int size) { int bigSeries[2] = { 0 }; calcSeries(arr, bigSeries,0, 0, 1, size -1, 1); printf("number of max parts going up %d \n", bigSeries[0]); } void calcSeries(int arr[], int bigSeries[],int originalCHeckedIndex, int checkedIndex, int currentIndex, int lastIndex, int ascending) { if ((checkedIndex == lastIndex) || (currentIndex > lastIndex)) { if (ascending > bigSeries[0]) bigSeries[0] = ascending; if (originalCHeckedIndex == lastIndex) return; else { calcSeries(arr, bigSeries, originalCHeckedIndex + 1, originalCHeckedIndex + 1, originalCHeckedIndex + 2, lastIndex, 0); return; } } if (arr[currentIndex] > arr[checkedIndex]) { calcSeries(arr, bigSeries, originalCHeckedIndex, currentIndex, currentIndex + 1, lastIndex, ascending + 1); } else { if (arr[originalCHeckedIndex] < arr[currentIndex]) calcSeries(arr, bigSeries, currentIndex, currentIndex, currentIndex + 1, lastIndex,ascending); calcSeries(arr, bigSeries, originalCHeckedIndex, checkedIndex, currentIndex + 1, lastIndex, ascending); } } 该算法与第一个答案有许多相似之处，但涵盖了一些您可能需要注意的极端情况。 我选择写一个新的答案，而不是写一篇冗长的评论。
理智检查
像在函数max_set（）中那样对arrays进行一些健全性检查。
- 是否提供了一个数组（检查为NULL）？
- 提供的数组大小是否至少为正（考虑size_t）？
允许的值
数据类型int允许正值和负值。 该算法应该处理两者。 至少我没有从你的post中读到他们必须是积极的。 如果你跳过那部分，我的代码看起来会更好一些。
递归
这个算法（以及第一个答案中的那个）的想法是递归地遍历数组，从第一个元素开始，最后结束。 因此，这已经定义了递归的开始和结束，如源代码中所述。
要以这种方式找到最长的数字子系列，总有三种可能性：
- 可以通过跳过当前处理的数字来访问最长的子系列
- 可以通过添加当前处理的数字来访问最长的子系列
- 当前处理的号码无法容纳
如果数字大于先前添加的最大数字，则可以添加数字; 毕竟我们正在寻找一个提升系列。 当前的数字可能比arrays中其他必须处理的数字要大。 所以我们必须考虑两种可能性：没有它和它的继续递归步骤 – 只要它符合标准。
可能的疏忽
考虑到INT_MIN（机器上可能的最小int值）是数组中完全有效的数字。 我添加了看到的变量，它只记录INT_MIN是否在数组中至少看过一次。 在第一次遇到时， 看到翻转从0到1，由于要求提升子系列，不允许任何进一步的INT_MIN值。 您的示例显示了此要求，其中两个出现了3。
测试
尝试找到各种测试用例，并有时考虑开箱即用。 数组为NULL，负大小，空数组。 接下来，添加像负数INT_MIN这样的奇特值。 或者创建升序系列，降序系列，隔行扫描。 数字发生多次……
#include #include int analyze(int arr[], int size, int min, int seen) { int sub_count = 0, count = 0; /* end of recursion */ if (size == 0) return 0; /* recursion step, without and with current number */ sub_count = analyze(arr + 1, size - 1, min, seen); if (arr[0] > min || (min == INT_MIN && arr[0] == INT_MIN && !seen)) count = 1 + analyze(arr + 1, size - 1, arr[0], arr[0] == INT_MIN); /* return length of largest sub-series */ return sub_count > count ? sub_count : count; } void max_set(int arr[], int size) { int seq = 0; if (arr != NULL && size > 0) { /* start of recursion */ seq = analyze(arr, size, INT_MIN, 0); } printf("max sequence is %d\n", seq); } int main(void) { int arr[] = { 45, 1, 21, 3, 3, 6, 53, 9, 18 }; max_set(arr, sizeof(arr) / sizeof(*arr)); return (0); }
#include int calcSeries(int arr[], int size, int value, int count){ int self, skip, rest; if(0 == size) return count; skip = calcSeries(arr + 1, size-1, value, count);//case of skip the top(self) if(value < *arr){ self = calcSeries(arr + 1, size-1, *arr, count+1);//case of include top if(skip > self) self = skip; } else self = skip; rest = calcSeries(arr + 1, size-1, -1, 0); return self > rest ? self : rest; } void max_set(int arr[], int size){ printf("number of max parts going up %d \n", calcSeries(arr, size, -1, 0)); } int main(void){ int array[]={45,1,21,3,3,6,53,9,18}; max_set(array, sizeof(array)/sizeof(*array)); return 0; }