<h2><a href="https://practice.geeksforgeeks.org/problems/maximum-sum-increasing-subsequence4749/1">Maximum sum increasing subsequence</a></h2><h3>Difficulty Level : Medium</h3><hr><div class="problems_problem_content__Xm_eO"><p><span style="font-size: 18px;">Given an array of <strong>n</strong> positive integers. Find the sum of the <strong>maximum sum subsequence</strong> of the given array such that the integers in the subsequence are sorted in strictly increasing order i.e. a <strong>strictly increasing subsequence</strong>.&nbsp;</span></p>
<p><span style="font-size: 18px;"><strong>Example 1:</strong></span></p>
<pre><span style="font-size: 18px;"><strong>Input</strong>: <br>N = 5, arr[] = {1, 101, 2, 3, 100} 
<strong>Output:</strong> <br>106
<strong>Explanation</strong>:<br>The maximum sum of a increasing sequence is obtained from {1, 2, 3, 100},</span></pre>
<p><span style="font-size: 18px;"><strong>Example 2:</strong></span></p>
<pre><span style="font-size: 18px;"><strong>Input</strong>: <br>N = 4, arr[] = {4, 1, 2, 3}
<strong>Output:</strong> <br>6
<strong>Explanation</strong>:<br>The maximum sum of a increasing sequence is obtained from {1, 2, 3}.</span></pre>
<p><span style="font-size: 18px;"><strong>Your Task:&nbsp;&nbsp;</strong><br>You don't need to read input or print anything. Complete the function <strong><code>maxSumIS</code>()&nbsp;</strong>which takes <strong>N </strong>and array <strong>arr </strong>as input parameters and returns the maximum value.</span></p>
<p><span style="font-size: 18px;"><strong>Expected Time Complexity:</strong> O(<strong>N<sup>2</sup></strong>)<br><strong>Expected Auxiliary Space:</strong> O(<strong>N</strong>)</span></p>
<p><span style="font-size: 18px;"><strong>Constraints:</strong><br>1 ≤ N ≤ 10<sup>3</sup></span><br><span style="font-size: 18px;">1 ≤ arr[i] ≤ 10<sup>5</sup></span></p></div><p><span style=font-size:18px><strong>Company Tags : </strong><br><code>Morgan Stanley</code>&nbsp;<code>Amazon</code>&nbsp;<code>Microsoft</code>&nbsp;<br><p><span style=font-size:18px><strong>Topic Tags : </strong><br><code>Dynamic Programming</code>&nbsp;<code>Algorithms</code>&nbsp;