資料結構
網路
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 次瀏覽
廣告