1. You are given an array of integers.
2. You have to find the sum of the subsequence which is strictly increasing and has the maximum sum.
3. For example,
Input : arr[] = {1, 101, 2, 3, 100, 4, 5}
Output : 106
Explanation : All the increasing subsequences are : (1,101); (1,2,3,100); (1,2,3,4,5). Out of these (1, 2, 3, 100) has the maximum sum = 106.
Note:
1. main takes input from the users.
2. This is a functional problem.
3. You have to complete the function maxSum. It takes as input an integer array. It should return the required sum.
4. Don't change the code of main and other utility functions.Input Format
First line takes input N, the length of the array. Second line takes input N space separated integers representing the elements of the array. Input is handled for you.
Output Format
The required sum. Output is handled for you.
Constraints
1 <= N <= 10^6
Notice
Try First, Check Solution later
1. You should first read the question and watch the question video.2. Think of a solution approach, then try and submit the question on editor tab.3. We strongly advise you to watch the solution video for prescribed approach.Example
Input
7 1 101 2 3 100 4 5
Output
106