数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法学C++程序：查找最大非递减子段的长度
假设我们有一个包含n个元素的数组A。Amal决定在互联网上做生意赚钱，一共n天。他在第i天赚到A[i]金额。Amal热爱进步，因此他想知道序列A[i]中最大非递减子段的长度。序列的子段是其连续片段。如果子段中的所有数字都是非递减顺序，则称其为非递减数字子段。
问题类别
在数据结构中，数组是特定类型元素的有限集合。数组用于将相同类型的元素存储在连续的内存位置中。数组被赋予特定的名称，并在各种编程语言中通过该名称引用。要访问数组的元素，需要索引。我们使用术语“name[i]”来访问数组“name”中位置“i”处的特定元素。可以使用数组实现各种数据结构，例如堆栈、队列、堆和优先队列。数组的操作包括插入、删除、更新、遍历、搜索和排序操作。点击以下链接了解更多信息。
https://tutorialspoint.com/data_structures_algorithms/array_data_structure.htm
因此，如果我们问题的输入类似于A = [2, 2, 1, 3, 4, 1]，则输出将为3，因为最大非递减子段是从第三个到第五个数字。
步骤
为了解决这个问题，我们将遵循以下步骤：
n := size of A y := A[0] d := 1 c := 1 for initialize i := 1, when i < n, update (increase i by 1), do: x := A[i] if x >= y, then: (increase d by 1) Otherwise d := 1 y := x c := maximum of c and d return c
示例
让我们看看下面的实现以更好地理解：
#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A){
int n = A.size();
int y = A[0];
int d = 1;
int c = 1;
for (int i = 1; i < n; i++){
int x = A[i];
if (x >= y)
d++;
else
d = 1;
y = x;
c = max(c, d);
}
return c;
}
int main(){
vector<int> A = { 2, 2, 1, 3, 4, 1 };
cout << solve(A) << endl;
}输入
{ 2, 2, 1, 3, 4, 1 }输出
3
更新于：2022年4月8日
666 次浏览
广告