《数据结构》--数组中升序有序子数组的最大长度

布满荆棘的人生 2022-12-29 14:06 118阅读 0赞

#include <iostream>
    
    int GetOrderLen(int arr[], int length)
    {
    	if (length < 0)
    		return 0;
    	else if (length < 2)
    		return 1;
    
    	int maxLen = 0; // 记录最长有序子数组
    	int currentLen = 0; //  当前记录的有序数组长度
    
    	for (int i = 0; i < length - 1; i++)
    	{
    		if (arr[i] < arr[i + 1])
    		{
    			currentLen++;
    		}
    		else
    		{
    			if (currentLen > maxLen)
    			{
    				maxLen = currentLen;
    			}
    			currentLen = 0;
    		}
    	}
    
    	return maxLen;
    }
    
    int main()
    {
    	// 测试用例1
    	const int length = 14;
    	int arr[length] = { 1, 7, 1, 2, 3, 5, 8, 11, 21, 31, 41, 1, 12, 6 };
    	std::cout << "maxLen: " << GetOrderLen(arr, length) << std::endl;
    	
    	// 测试用例2
    	const int length1 = 31;
    	int arr1[length1] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 33, 1, 11, 7, 1, 2, 3, 5, 8, 11, 21, 31, 41, 1, 12, 6 };
    	std::cout << "maxLen: " << GetOrderLen(arr1, length1) << std::endl;
    
    	// 测试用例3
    	const int length2 = 1;
    	int arr2[length2] = {};
    	std::cout << "maxLen: " << GetOrderLen(arr2, length2) << std::endl;
    }

计算复杂度为 O(n)。

张先超先生在书中给的伪代码计算复杂度是O(n2)。

发表评论取消回复

表情：

评论列表（有 0 条评论，118人围观）

还没有评论，来说两句吧...

相关阅读

相关 1800. 最大升序子数组和

题目链接：[https://leetcode.cn/problems/maximum-ascending-subarray-sum/][https_leetcode.cn_pr

ゝ一纸荒年。/ 2024年04月03日 09:48/ 0 赞/ 57 阅读

相关最长的可整合子数组的长度

最长的可整合子数组的长度我使用了最笨的暴力方法，根据题目描述直接得到答案。 import java.util.Scanner; public class

以你之姓@/ 2023年07月06日 08:57/ 0 赞/ 14 阅读

相关《数据结构》--数组中升序有序子数组的最大长度

include <iostream> int GetOrderLen(int arr[], int length) { if (le

布满荆棘的人生/ 2022年12月29日 14:06/ 0 赞/ 119 阅读

相关数组中最长升序子序列python_查找数组中最长的升序序列（Python）

我的解决方案：def best\_sequence\_length(arr): '''Find length of the longest ascending sequenc

短命女/ 2022年11月01日 10:52/ 0 赞/ 138 阅读

相关最大子数组和

/ 输入一个整数数组nums，请在其中找一个和最大的子数组动态规划定义dp数组：dp[i]是以num[i]结尾的最大子数组和 / public cla

矫情吗；*/ 2022年10月29日 10:28/ 0 赞/ 207 阅读

相关最大子数组和

/ 输入一个整数数组nums，请你在其中找一个和最大的子数组，返回这个子数组的和 dp[i]表示以nums[i]的最大子数组和状态 / public c

青旅半醒/ 2022年10月27日 13:49/ 0 赞/ 213 阅读

相关【数据结构与算法面试题】子数组的最大和

> 题目来源“[数据结构与算法面试题80道][80]”。 > ![这里写图片描述][946f781033f9454736251ff3d35f5223.png] 问题分析：

忘是亡心i/ 2022年10月07日 03:53/ 0 赞/ 153 阅读

相关数组中最长的升序子序列

2016喜马拉雅校园招聘笔试题？好像是，记不太清除了属于 Dynamic programming 的范畴 [The longest Increasing Subseque

我不是女神ヾ/ 2022年08月09日 13:40/ 0 赞/ 184 阅读

相关 java中数组的最大长度以及List的最大容量

java 中数组的最大长度是多少呢？看一下它的length属性就可以了。length属性是32位的有符号整数，它的最大值是2的31次幂，就是2G。为何有这个限制

- 日理万妓/ 2022年06月04日 01:17/ 0 赞/ 1243 阅读

相关数据结构-最大连续子数组

【题目来自灰灰考研】在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的

矫情吗；*/ 2022年05月19日 09:40/ 0 赞/ 228 阅读