資料結構
網路
關係資料庫管理系統 (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.tw/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 次瀏覽
廣告