MAXIMUM SUM INCREASING SUB SEQUENCE(GEEKS FOR GEEKS)

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 intgers in the subsequence are sorted in increasing order.

Input:

The first line of input contains an integer T denoting the number of test cases.
The first line of each test case is N,N is the size of array.
The second line of each test case contains N input A[].

Output:

Print the sum of maximum sum sequence of the given array.

Constraints:

1 ≤ T ≤ 50
1 ≤ N ≤ 100
1 ≤ A[] ≤ 1000

Example:

Input:
2
7
1 101 2 3 100 4 5
4
10 5 4 3

Output:
106
10

CODE:

#include<stdio.h>

int maxSumIS( int arr[], int n )

{

    int i, j, max = 0;

    int msis[n];

   

    for ( i = 0; i < n; i++ )

        msis[i] = arr[i];

   

    for ( i = 1; i < n; i++ )

        for ( j = 0; j < i; j++ )

            if ( arr[i] > arr[j] && msis[i] < msis[j] + arr[i])

                msis[i] = msis[j] + arr[i];

    

    for ( i = 0; i < n; i++ )

        if ( max < msis[i] )

            max = msis[i];

    return max;

}

int main()

{

   int t,i;

   scanf("%d",&t);

   while(t--)

    {

    int n;

    scanf("%d",&n);

    int a[n];

    for(i=0;i<n;i++)

     scanf("%d",&a[i]);

    printf("%d\n",maxSumIS( a, n ) );

    }

    return 0;

}