C++ 中双调子数组的最大和
c++server side programmingprogramming
在这个问题中，我们给定一个数组 arr[]。我们的任务是编写一个程序，用 C++ 语言找出双调子数组的最大和。
双调子数组是一种特殊的子数组，其中元素严格先增加，达到某个值后严格减少。
让我们举个例子来理解这个问题:
输入
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<<"双调子数组的最大和为 "<<findMaxSumBiTonicSubArr(arr, N);
return 0;
}
输出
双调子数组的最大和为 30
