建网站引流做淘宝,几个小时学wordpress,嘉兴网站排名优化报价,网站后台如何更新1.题目描述
在数列 a1,a2,⋯,an 中#xff0c;如果aiai1ai2⋯aj#xff0c;则称 ai 至 aj 为一段递增序列#xff0c;长度为 j−i1。
定一个数列#xff0c;请问数列中最长的递增序列有多长。
输入描述
输入的第一行包含一个整数 n。…1.题目描述
在数列 a1,a2,⋯,an 中如果aiai1ai2⋯aj则称 ai 至 aj 为一段递增序列长度为 j−i1。
定一个数列请问数列中最长的递增序列有多长。
输入描述
输入的第一行包含一个整数 n。
第二行包含 n 个整数 a1,a2,⋯,an相邻的整数间用空格分隔表示给定的数列。
其中 2≤n≤10000≤数列中的数≤104。
输出描述:
输出一行包含一个整数表示答案。
输入输出样例
示例 输入 7
5 2 4 1 3 7 2输出 3运行限制
最大运行时间1s最大运行内存: 256M
2.代码
#include iostream // 引入输入输出流库
using namespace std; // 使用标准命名空间int main() // 主函数
{int n; // 定义一个整数n用于存储数列的长度cin n; // 从标准输入读取n的值int a[n2]; // 定义一个大小为n2的整数数组a用于存放数列多开两个空间以防止越界int len 1, maxn 1; // 定义两个整数len和maxn分别用于记录当前递增序列的长度和最长递增序列的长度初始值都设为1for (int i 0; i n; i) // 循环读取n个整数并存入数组a中{cin a[i];}for (int i 1; i n; i) // 从数组的第二个元素开始遍历{if (a[i] a[i - 1]) // 如果当前元素大于前一个元素说明递增序列还在继续{len; // 递增序列长度加1if (i n - 1 maxn len) // 如果当前元素是数组的最后一个元素并且当前递增序列长度大于已知的最长递增序列长度{maxn len; // 更新最长递增序列长度}}else // 如果当前元素不大于前一个元素说明递增序列结束{if (maxn len) // 如果当前递增序列长度大于已知的最长递增序列长度{maxn len; // 更新最长递增序列长度}len 1; // 重置当前递增序列长度为1}}cout maxn endl; // 输出最长递增序列的长度return 0; // 返回0表示程序正常结束
}
3.解题想法
以上代码的思路主要是通过一次遍历来找出数列中的最长递增子序列的长度。具体来说它使用了一个变量len来记录当前递增序列的长度另一个变量maxn来记录最长递增序列的长度。遍历数列时如果当前元素大于前一个元素则len加1否则将len与maxn比较并更新maxn然后将len重置为1。
优点 1. 简单直观代码逻辑清晰容易理解和实现。
2. 时间复杂度低只需遍历一次数列时间复杂度为O(n)效率较高。
3. 空间复杂度低只使用了常数级别的额外空间空间复杂度为O(1)。
缺点 1. 边界条件处理复杂需要特别处理最后一个元素的递增序列情况增加了代码的复杂性。
2. 不够灵活如果需要处理更复杂的序列问题如最长非递减子序列需要对代码进行较大修改。
枚举法的改进 如果你希望在找到一个递增序列后能够从下一个元素开始继续查找而不是从头开始可以使用动态规划的方法来改进。具体来说可以使用一个数组dp来记录以每个元素结尾的最长递增子序列的长度。
