This problem is a variation of LIS i.e. longest increasing subsequence problem, we will use recursion approach first to solve the problem:

We have following option with us for each element of the array.

1. Either we can include the given array element if it is greater than the previous element in the increasing subsequence function.
2. We can exclude the current array element and recursively solve for the remaining items.

We pick the maximum value obtained from the above two options in our final answer.
Here we are using the solve function to calculate the maximum sum increasing subsequences.

arr[]=is the input array.

The index i is the index, n is the size of the array, prev is the previous sum and sum is the total maximum sum increasing subsequences that we got.

The recursive function will terminate when the index reaches the end of the array if we start to solve from left and if we start from right then the base condition will be if the index is <0.

Time complexity for the above approach in the worst case is exponential

Space complexity for the above approach in the worst case is: O(1)

Dynamic Programming Approach:

In this approach we will use the same logic as Longest increasing subsequence problem, we will create an array sum[] as the same size as of the given array arr[], we will store the value sum[i] as the maximum sum of an increasing subsequence of subarray arr[0...i] that ends with arr[i].

To calculate the sum[i] we will check the maximum sum increasing subsequence of all the smaller values of i that had already been calculated and then we pick the maximum of them.

Time complexity for the above approach in the worst case is : O(n*n)
Space complexity for the above approach in the worst case is: O(n)

C++ Implementation (Recursion approach):

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

//declare function solve.
ll solve(ll arr[], ll index, ll n, ll previous, ll sum)
{
    //base condition if we
    //reached ahead of last element.
    if (index == n)
        return sum;

    //if we are not including current
    //element.
    ll s1 = solve(arr, index + 1, n, previous, sum);

    //if we are including current element.
    ll s2 = sum; //check condition.
    if (arr[index] > previous)
        s2 = solve(arr, index + 1, n, arr[index], sum + arr[index]);

    //return maximum value
    //from two option.
    return max(s1, s2);
}

int main()
{
    ll t;
    cout << "Enter number of test cases: ";
    cin >> t;

    while (t--) {
        cout << "Enter size of array: ";
        ll n;
        cin >> n;

        ll arr[n];

        cout << "Enter array elements: ";
        for (ll i = 0; i < n; i++)
            cin >> arr[i];

        cout << "Maximum sum increasing subsequence: ";
        cout << solve(arr, 0, n, INT_MIN, 0) << "\n";
    }

    return 0;
}

Output:

Enter number of test cases: 3
Enter size of array: 5
Enter array elements: 1 2 3 4 5
Maximum sum increasing subsequence: 15
Enter size of array: 3
Enter array elements: 10 9 20
Maximum sum increasing subsequence: 30
Enter size of array: 4
Enter array elements: 2 5 1 0 5
Maximum sum increasing subsequence: 7

C++ Implementation (Dynamic Programming):

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

//solve function to calculate
//maximum sum increasing subsequence.
ll solve(ll arr[], ll n)
{
    //initialize sum array with same
    //size as that of given array.
    ll sum[n];

    //initialize each element of sum
    //with same as arr[i].
    for (ll i = 0; i < n; i++)
        sum[i] = arr[i];

    //start iterating from second
    //element till last element.
    for (ll i = 1; i < n; i++) {

        //compare all smaller elements
        //than current element.
        for (ll j = 0; j < i; j++) {

            //check for LIS condition.
            if (arr[i] > arr[j] and sum[i] < sum[j] + arr[i])
                sum[i] = sum[j] + arr[i];
        }
    }
 
    //find maximum value by iterating.
    ll ans = *max_element(sum, sum + n);
 
    //return ans.
    return ans;
}

int main()
{
    ll t;
    cout << "Enter number of test cases: ";
    cin >> t;
    
    while (t--) {
        cout << "Enter size of array: ";
        ll n;
        cin >> n;
    
        ll arr[n];
    
        cout << "Enter elements: ";
        for (ll i = 0; i < n; i++)
            cin >> arr[i];
    
        cout << "Maximum sum increasing subsequence: ";
        cout << solve(arr, n) << "\n";
    }
    
    return 0;
}

Output:

Enter number of test cases: 3
Enter size of array: 5
Enter elements: 10 9 8 7 6  
Maximum sum increasing subsequence: 10
Enter size of array: 3
Enter elements: 1 2 3
Maximum sum increasing subsequence: 6
Enter size of array: 5
Enter elements: 9 18 2 4 10
Maximum sum increasing subsequence: 27