Modify the Provided code such that it also prints the decreasing max sum sequence right after increasing sequence finish

Business, Finance, Economics, Accounting, Operations Management, Computer Science, Electrical Engineering, Mechanical Engineering, Civil Engineering, Chemical Engineering, Algebra, Precalculus, Statistics and Probabilty, Advanced Math, Physics, Chemistry, Biology, Nursing, Psychology, Certifications, Tests, Prep, and more.
Post Reply
answerhappygod
Site Admin
Posts: 899604
Joined: Mon Aug 02, 2021 8:13 am

Modify the Provided code such that it also prints the decreasing max sum sequence right after increasing sequence finish

Post by answerhappygod »

Modify the Provided code such that it also prints the decreasing
max sum sequence right after increasing sequence finished. The
output should be 1 2 3 6 7 9 10 2 1
#include <iostream>
#include <vector>
using namespace std;
int findSum(vector<int> arr){
int sum = 0;
for (int i=0;i<arr.size();i++)
sum += arr;
return sum;
}
// Function to construct Maximum Sum Increasing
// Subsequence
void printMaxSumIS(int arr[], int n)
{
// L - The Maximum Sum Increasing
// Subsequence that ends with arr
vector<vector<int> > L(n);
// L[0] is equal to arr[0]
L[0].push_back(arr[0]);
// start from index 1
for (int i = 1; i < n; i++) {
// for every j less than i
for (int j = 0; j < i; j++) {

if ((arr > arr[j])
&& (findSum(L) < findSum(L[j])))
L =
L[j];
}
// L ends with arr
L.push_back(arr);
// L[i] now stores Maximum Sum
Increasing
// Subsequence of arr[0..i] that ends
with
// arr[i]
}
vector<int> res = L[0];
// find max
for (vector<int> x : L)
if (findSum(x) > findSum(res))
res = x;
// max will contain result
for (int i : res)
cout << i << " ";
cout << endl;
}
// Driver Code
int main()
{
int arr[] = { 1 ,2, 3, 8, 6, 7, 9, 10, 2, 1,4
};
int n = sizeof(arr) / sizeof(arr[0]);
// construct and print Max Sum IS of arr
printMaxSumIS(arr, n);
return 0;
}
Join a community of subject matter experts. Register for FREE to view solutions, replies, and use search function. Request answer by replying!
Post Reply