C ++中的最大和子位子数组

在这个问题上，我们得到了一个数组arr []。我们的任务是创建一个程序，以查找C ++中最大的总和子位子数组。

Bitonic子数组是一种特殊的子数组，其中元素首先严格增加，然后在达到特定点后严格减少。

让我们举个例子来了解这个问题，

输入项

arr[] = {4, 2, 3, 7 ,9, 6, 3, 5, 1}

输出结果

30

说明

双音子数组是[2、3、7、9、6、3]。总和= 2 + 3 + 7 + 9 + 6 + 3 = 30

解决方法

该解决方案类似于双子序列问题。我们将创建两个数组incSubArr []和decSubArr []。这将创建存储增加和减少的子数组。在索引i处，incSubArr [i]将找到从0到i递增的子数组。decSubArr [i]将发现从i到N的子数组不断增加。

maxSum是计算为（incSubArr [i] + decSubArr [i]-arr [i]）的最大值。

示例

该程序说明了我们解决方案的工作原理，

#include <iostream>
using namespace std;
int findMaxSumBiTonicSubArr(int arr[], int N){
   int incSubArr[N], decSubArr[N];
   int max_sum = -1;
   incSubArr[0] = arr[0];
   for (int i=1; i<N; i++)
      if (arr[i] > arr[i-1])
         incSubArr[i] = incSubArr[i-1] + arr[i];
      else
         incSubArr[i] = arr[i];
   decSubArr[N-1] = arr[N-1];
   for (int i= (N-2); i>=0; i--)
      if (arr[i] > arr[i+1])
         decSubArr[i] = decSubArr[i+1] + arr[i];
      else
         decSubArr[i] = arr[i];
   for (int i=0; i<N; i++)
      if(max_sum < (incSubArr[i] + decSubArr[i] - arr[i]))
max_sum = incSubArr[i] + decSubArr[i] - arr[i];
   return max_sum;
}
int main(){
   int arr[] = {4, 2, 3, 7 ,9, 6, 3, 5, 1};
   int N = sizeof(arr) / sizeof(arr[0]);
   cout<<"The Maximum Sum of Bitonic Subarray is "<<findMaxSumBiTonicSubArr(arr, N);
   return 0;
}

输出结果

The Maximum Sum of Bitonic Subarray is 30