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;
}
Modify the Provided code such that it also prints the decreasing max sum sequence right after increasing sequence finish
-
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
Join a community of subject matter experts. Register for FREE to view solutions, replies, and use search function. Request answer by replying!