数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装学
法学C++中从前缀和给定元素之后的前缀的最大和递增子序列
在这个问题中，我们给定一个包含N个整数的数组arr[]以及两个索引值x和y。我们的任务是创建一个程序，用C++查找从前缀到给定元素之后的前缀的最大和递增子序列。
问题描述
我们将找到直到索引x且包括索引y处的元素的递增序列的最大和。
让我们来看一个例子来理解这个问题：
输入
arr[] = {1, 5, 9, 131, 6, 100, 11, 215}, x = 4, y = 6输出
26
解释
我们将取直到索引3的子序列，然后最后包含arr[6] = 11。
子序列是{1, 5, 9, 11}。和 = 1+5+9+11 = 26
解决方案方法
一种简单的方法是创建一个直到索引x的新数组，然后在末尾添加索引y处的元素。然后计算所有递增子序列，然后丢弃所有不能包含元素arr[y]的子序列，并找到maxSum。
另一种有效的方法是使用动态规划方法。其思想是创建一个二维数组DP[][]，并存储递增子序列的最大和。DP[x][y]的值将给出直到索引x且包括元素arr[y]的最大和。
示例
程序演示了我们解决方案的工作原理：
#include <iostream>
using namespace std;
int DP[100][100];
void preCalcMaxSum(int arr[], int N){
for (int i = 0; i < N; i++) {
if (arr[i] > arr[0])
DP[0][i] = arr[i] + arr[0];
else
DP[0][i] = arr[i];
}
for (int i = 1; i < N; i++) {
for (int j = 0; j < N; j++) {
if (arr[j] > arr[i] && j > i) {
if (DP[i - 1][i] + arr[j] > DP[i - 1][j])
DP[i][j] = DP[i - 1][i] + arr[j];
else
DP[i][j] = DP[i - 1][j];
}
else
DP[i][j] = DP[i - 1][j];
}
}
}
int main() {
int arr[] = {1, 5, 9, 131, 6, 100, 11, 215};
int N = sizeof(arr) / sizeof(arr[0]);
int x = 4, y = 6;
preCalcMaxSum(arr, N);
cout<<"The maximum sum increasing subsequence from a prefix and a given element after prefix is must is ";
cout<<DP[x][y];
return 0;
}输出
The maximum sum increasing subsequence from a prefix and a given element after prefix is must is 26
一种**有效的方法**是找到直到索引x的递增子序列的最大和，使得序列的最大元素小于索引y处的元素。为此，我们将再次使用动态规划方法。
示例
程序演示了我们解决方案的工作原理：
#include <iostream>
using namespace std;
int calcMaxSum(int arr[], int n, int x, int y){
int DP[x] = {0};
int maxSum = -1;
for (int i = 0; i <= x; i++)
DP[i] = arr[i];
for (int i = 0; i <= x; i++) {
if (arr[i] >= arr[y]) {
continue;
}
for (int j = 0; j < i; j++) {
if (arr[i] > arr[j])
DP[i] += arr[j];
maxSum = max(maxSum, DP[i]);
}
}
if (maxSum == -1) {
return arr[y];
}
return maxSum + arr[y];
}
int main(){
int arr[] = {1, 5, 9, 131, 6, 100, 11, 215};
int N = sizeof(arr) / sizeof(arr[0]);
int x = 4, y = 6;
cout<<"The maximum sum increasing subsequence from a prefix and a given element after prefix is must is ";
cout<<calcMaxSum(arr, N, x, y);
return 0;
}输出
The maximum sum increasing subsequence from a prefix and a given element after prefix is must is 26
更新于：2020年10月15日
106 次浏览
广告