資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝學
法學C++ 中最大和遞減子序列
在本文中，我們給定一個包含 N 個整數的陣列 arr[]。我們的任務是在 C++ 中找到最大和遞減子序列。
最大和遞減子序列 (MSDS) 是給定陣列序列的一個子序列。此處序列元素按遞減順序排列，這些元素的和最大。
在這裡，給定一個數組序列 a1,a2,…, an，目標是找到一個子序列 ai1,ai2,…,aik，其中 i1>i2>…>i1，這樣我們就說子序列是 ai1>ai2>…>aik（按遞減順序排列）。項 ai1+(ai2)...+(aik) 的序列向所有遞減序列中的較高值偏移，較低的項始終繫結較高的項。
讓我們剖析一下定義：
- 子序列：子序列是從源序列派生的序列，可以透過保留所有元素或消除其中一些元素而不改變其順序來得到。
- 遞減順序：這是數字在 MSDS 中排列的順序，並且在此特定順序中，每個數字都小於前一個數字。
- 最大和：MSDS 是具有最大可能和的序列。數字序列是子序列中遞減元素的總和。
以下是查詢 C++ 中遞減子序列的最大和的輸入-輸出場景：
輸入
arr[] = {3, 1, 6, 10, 5, 3, 2, 9, 1}
輸出
21
解釋
最大和的遞減子序列是 {10, 5, 3, 2, 1} = 10 + 5 + 3 + 2 + 1 = 21
解決方案方法
我們將找到陣列中元素的最大和，使得子序列嚴格遞減。
因此，這裡我們將使用動態規劃方法來找到解決方案。在這裡，我們將建立一個 maxSum[] 陣列，它將儲存直到索引 i 的 maxSum。使用以下公式來查詢陣列值：
maxSum[i] = arr[i] + max(maxSum[0 … (*i-1)])
最大和由陣列 maxSum[] 的最大元素給出。
示例
以下程式演示了 C++ 中最大和遞減子序列：
#include <iostream>
using namespace std;
int findMaxSumDecSubSeq(int arr[], int N){
int maximumSum = 0;
int maxSum[N];
for (int i = 0; i < N; i++)
maxSum[i] = arr[i];
for (int i = 1; i < N; i++)
for (int j = 0; j < i; j++)
if (arr[i] < arr[j] && maxSum[i] < maxSum[j] + arr[i])
maxSum[i] = maxSum[j] + arr[i];
for (int i = 0; i < N; i++)
if (maximumSum < maxSum[i])
maximumSum = maxSum[i];
return maximumSum;
}
int main(){
int arr[] = { 3, 1, 6, 10, 5, 3, 2, 9, 1 };
int N= sizeof(arr) / sizeof(arr[0]);
cout<<"The maximum sum of decreasing subsequence is "<<findMaxSumDecSubSeq(arr, N);
return 0;
}
輸出
The maximum sum of decreasing subsequence is 21
更新於：2024年5月22日
278 次瀏覽
廣告