# Maximum Sum Increasing Subsequence

Given an array of n positive integers. Write a program to find the sum of maximum sum subsequence of the given array such that the integers in the subsequence are sorted in increasing order. For example, if input is {1, 101, 2, 3, 100, 4, 5}, then output should be 106 (1 + 2 + 3 + 100), if the input array is {3, 4, 5, 10}, then output should be 22 (3 + 4 + 5 + 10) and if the input array is {10, 5, 4, 3}, then output should be 10

```java
class GFG {
    public static int maxSum(int[] arr) {
        // dp[i] -> Max increasing subsequence sum upto i, including 'i'
        int dp[] = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            dp[i] = arr[i];
            for (int j = 0; j < i; j++)
                if (arr[j] < arr[i])
                    dp[i] = Math.max(dp[j] + arr[i], dp[i]);
        }
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++)
            max = Math.max(max, dp[i]);
        return max;
    }
}
```
