Please help write a C++ function( With only the standard libraries:iostream and
ID: 3870614 • Letter: P
Question
Please help write a C++ function(With only the standard libraries:iostream and vector) ,void maxinc (int *nums, int n) which accepts an integer array, nums, and the length of the array n,which is a positive integers. It will then prints out a single line of the maximum length increasing sequence in the input array. An increasing sequence is defined as a sequence of numbers increasing in magnitude. If multiple maximum length increasing sequences exist in the input array, then the function should print out the one with the largest total sum. The elements of the array are unique.
For example, if my input array nums = [1 5 3 2 4] and n = 5, the function will print the sequence 1, 3 ,4;
Another example: if nums = [ 7 4 3 10 33 8] and n = 6, then the function will print 7, 10 ,33.( not 4 10 33)
Explanation / Answer
#include <iostream>
#include <vector>
using namespace std;
void printMaxLenIncrSequence(vector<int>& arr)
{
for (int i=0;i<arr.size();i++)
cout << arr[i] << " ";
cout << endl;
}
void maxinc(int *arr, int n)
{
// The longest increasing sub-sequence
vector<vector<int> > LongestSubSeq(n);
LongestSubSeq[0].push_back(arr[0]);
// start from index 1
for (int i = 1; i < n; i++)
{
// do for every j less than i
for (int j = 0; j < i; j++)
{
if ((arr[i] > arr[j]) &&
(LongestSubSeq[i].size() < LongestSubSeq[j].size()))
LongestSubSeq[i] = LongestSubSeq[j];
}
LongestSubSeq[i].push_back(arr[i]);
}
// L[i] now stores increasing sub-sequence of
// arr[0..i] that ends with arr[i]
vector<int> max = LongestSubSeq[0];
for (vector<int> x : LongestSubSeq)
if (x.size() > max.size())
max = x;
// max will contain LIS
printMaxLenIncrSequence(max);
}
// Driver function
int main()
{
int arr_01[] = { 1, 5, 3, 2, 4 };
int arr_02[] = { 7, 4, 3, 10,33,8};
int n_01 = 5;
int n_02 = 6;
maxinc (arr_01, n_01);
maxinc (arr_02, n_02);
return 0;
}
OUTPUT: