数据结构
网络
关系数据库管理系统 (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 次浏览
广告