数据结构
网络
关系数据库管理系统 (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 次浏览
广告