title: Dynamic Programming Set 14 Maximum Sum Increasing Subsequence
signature: dynamic_programming_set_14_maximum_sum_increasing_subsequence <- function(arr, n) {
source_py: def dynamic_programming_set_14_maximum_sum_increasing_subsequence(arr, n):
      max = 0
      msis = [0 for x in range(n)]
      for i in range(n):
          msis[i] = arr[i]
      for i in range(1, n):
          for j in range(i):
              if ((arr[i] > arr[j]) and (msis[i] < (msis[j] + arr[i]))):
                  msis[i] = (msis[j] + arr[i])
      for i in range(n):
          if (max < msis[i]):
              max = msis[i]
      return max
source_cpp: int dynamic_programming_set_14_maximum_sum_increasing_subsequence(vector<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;
  }