C++ 中最大和递减子序列
c++server side programmingprogramming
在这个问题中，我们给定一个包含 N 个整数的数组 arr[]。我们的任务是在 C++ 中找出最大和递减子序列。
问题描述
我们将从数组中找到元素和的最大值，使得子序列严格递减。
我们举个例子来理解这个问题:
输入
arr[] = {3, 1, 6, 10, 5, 2, 9}
输出
17
解释
和最大的递减子序列是 {10, 5, 2} = 10 + 5 + 2 = 17
解决方法
在这里，我们将使用动态规划方法求解。这里，我们将创建一个 maxSum[] 数组，用于存储直到索引 i 的最大和。以下公式用于查找数组值:
maxSum[i] = arr[i] + max(maxSum[0 … (*i-1)])
最大和由数组 maxSum[] 中的最大元素给出。
示例
编写程序来演示我们的解决方案的工作原理:
#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[] = { 5, 4, 100, 3, 2, 101, 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 106
