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