满足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

解决方法

从示例中我们可以看出，对于任何条件都为真。子数组应具有交替的大小较小的元素，即如果1st> 2nd，则2nd> 3rd，依此类推。

现在，为了便于计算，我们将创建一个指示此关系的关系数组。以下是我们将如何定制关系数组的方法，

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