数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程语言
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济
心理学
社会研究
时尚研究
法律研究C++ 中的最大总和比特尼子数组
在本问题中，我们得到一个数组 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<<"The Maximum Sum of Bitonic Subarray is "<<findMaxSumBiTonicSubArr(arr, N);
return 0;
}输出
The Maximum Sum of Bitonic Subarray is 30
更新于： 2020 年 10 月 15 日
387 次浏览
广告