Given an array Arr[], the task is to find the maximum sum of all the elements which are not a part of the longest increasing subsequence.
Example 1:
Input:
n = 6
Arr = {4, 6, 1, 2, 4, 6}
Output: 10
Explaination: Elements are 4 and 6.
Example 2:
Input:
n = 5
Arr = {5, 4, 3, 2, 1}
Output: 14
Explaination: Elements are 5,4,3 and 2.
Your Task:
You don't need to read input or print anything. Your task is to complete the function maxSumLis() which takes the array Arr[] and its size n as input parameters and returns maximum sum of elements not part of LIS.
Expected Time Complexity: O(n^{2})
Expected Auxiliary Space: O(n)
Constraints:
1 ≤ N ≤ 1000
1 ≤ Arr[i] ≤ 10^{5}

见题面

见题面