資料結構
網路
關係資料庫管理系統 (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}輸出
33
解釋
產生最大和的雙調子序列是 {2, 3, 7, 9, 6, 5, 1} 和 = 2 + 3 + 7 + 9 + 6 + 5 + 1 = 33
解決方案方法
為了找到最大和雙調子序列，我們將建立兩個陣列 incSeq[] 和 decSeq[]，這樣對於索引處的元素 i，incSeq[i] 包含從 arr[0…i] 中嚴格遞增的所有元素的和，而 decSeq[i] 包含從 arr[i…n] 中嚴格遞減的所有元素的和。
最後，我們將返回 maxSum 作為 (incSeq[i] + decSeq[i] - arr[i]) 的最大值。
示例
程式來說明我們解決方案的措辭：
#include <iostream>
using namespace std;
int calcMaxVal(int a, int b){
if(a > b)
return a;
return b;
}
int findMaxSumBiTonicSubSeq(int arr[], int N){
int maxSum = -1;
int incSeq[N], decSeq[N];
for (int i = 0; i < N; i++){
decSeq[i] = arr[i];
incSeq[i] = arr[i];
}
for (int i = 1; i < N; i++)
for (int j = 0; j < i; j++)
if (arr[i] > arr[j] && incSeq[i] < incSeq[j] + arr[i]) incSeq[i] = incSeq[j] + arr[i];
for (int i = N - 2; i >= 0; i--)
for (int j = N - 1; j > i; j--)
if (arr[i] > arr[j] && decSeq[i] < decSeq[j] + arr[i])
decSeq[i] = decSeq[j] + arr[i];
for (int i = 0; i < N; i++)
maxSum = calcMaxVal(maxSum, (decSeq[i] + incSeq[i] - arr[i]));
return maxSum;
}
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 Bi-tonic subsequence is : "<<findMaxSumBiTonicSubSeq(arr, N);
return 0;
}輸出
The Maximum Sum of Bi-tonic subsequence is : 33
更新於：2020年10月15日
141 次檢視
廣告