Question

Problem Statement
Given an array A of Nintegers your friend asks you to find the maximum sum of
elements of any special LIS in A. It is given that a special LiS is an LIS but with non-
decreasing elements instead of strictly increasing elements
It is given that you are not allowed to rearrange the elements in A in any manner while
finding the special Longest increasing Subsequence'uis described above.

Answer 1

Explanation:

Problem Description: A subsequence is derived from an array by deleting a few of its elements and not changing the order of remaining elements. You are given an array A with N elements, write a program to find the longest increasing subsequence in the array.

An increasing subsequence is a subsequence with its elements in increasing order. You need to find the length of the longest increasing subsequence that can be derived from the given array.

For example:

Input: A = {3, 10, 2, 1, 20}

Output: 3

Explanation: The longest increasing subsequence is {3,10,20}.

Input: A = {10, 2, 5, 3, 7, 101, 18}

Output: 4

Explanation: The longest incresing subsequence is {2,3,7,101} or {2,3,7,18} or {2,5,7,101} or {2,5,7,18}.