資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
Microsoft Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++程式中滿足給定條件的最大子陣列大小
在這個問題中，我們給定一個包含n個整數的陣列arr[]。我們的任務是建立一個程式來查詢滿足給定條件的最大子陣列的大小。
問題描述 - 我們需要找到滿足以下任一條件的最大子陣列的長度：
如果k是奇數，則arr[k] > arr[k+1]；如果k是偶數，則arr[k] < arr[k+1]。對於子陣列的所有元素。
如果k是奇數，則arr[k] < arr[k+1]；如果k是偶數，則arr[k] > arr[k+1]。對於子陣列的所有元素。
這裡，k是arr[]中子陣列元素的索引。
讓我們舉個例子來理解這個問題：
輸入
arr[] = {7, 3, 1, 5, 4, 2, 9}輸出
4
解釋
The subarray {3, 1, 5, 4} satisfies the condition 1.
k = 1(odd), arr[k] > arr[k+1], 3 > 1
k = 2(even), arr[k] < arr[k+1], 1 < 5
k = 3(odd), arr[k] > arr[k+1], 5 > 4解決方案方法
我們可以從例子中看出，為了使任何條件都成立，子陣列應該具有交替的“大於-小於”元素，即如果第一個元素>第二個元素，則第二個元素>第三個元素，依此類推。
現在，為了方便計算，我們將建立一個關係陣列來指示這種關係。我們將按如下方式調整關係陣列：
If arr[i] == arr[i + 1],relArr[i] = ‘E’ If arr[i] > arr[i + 1],relArr[i] = ‘G’ If arr[i] < arr[i + 1],relArr[i] = ‘S’
使用這個陣列，我們可以很容易地找到最大的子陣列大小。要考慮的子陣列將具有交替的“G”和“S”。
示例
程式演示了我們解決方案的工作原理：
#include<iostream>
using namespace std;
char findRel(int a, int b) {
if(a > b)
return 'G';
else if(a < b)
return 'S';
return 'E';
}
int calcMaxSubArray(int arr[], int n) {
int maxLen = 1;
int len = 1;
char c = findRel(arr[0], arr[1]);
for(int i = 1; i <= n−1; i++){
if(c == 'S' && findRel(arr[i], arr[i + 1]) == 'G')
len++;
else if(c == 'G' && findRel(arr[i], arr[i + 1]) == 'S')
len++;
else {
if(maxLen < (len + 1))
maxLen = (len + 1);
len = 1;
}
c = findRel(arr[i], arr[i+1]);
}
return maxLen;
}
int main() {
int arr[] = {7, 3, 1, 5, 4, 2, 9};
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"The maximum size of sub−array that satisfies the given
condition is "<<calcMaxSubArray(arr, n);
}輸出
The maximum size of sub-array that satisfies the given condition is 4
更新於：2020年12月9日
124 次瀏覽
廣告