Dynamic Programming | Set 14 (Maximum Sum Increasing Subsequence) | GeeksforGeeks

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.

We need a slight change in the Dynamic Programming solution of LIS problem. All we need to change is to use sum as a criteria instead of length of increasing subsequence.

int maxSumIS( int arr[], int n )

{

   int *msis, i, j, max = 0;

   msis = (int*) malloc ( sizeof( int ) * n );

   /* Initialize msis values for all indexes */

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

      msis[i] = arr[i];

   /* Compute maximum sum values in bottom up manner */

   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];

   /* Pick maximum of all msis values */

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

      if ( max < msis[i] )

         max = msis[i];

   /* Free memory to avoid memory leak */

   free( msis );

   return max;

}

Read full article from Dynamic Programming | Set 14 (Maximum Sum Increasing Subsequence) | GeeksforGeeks