title: Dynamic Programming Set 14 Maximum Sum Increasing Subsequence
signature: int dynamicProgrammingSet14MaximumSumIncreasingSubsequence(vector<int> arr, int n) {
test_code: #include <algorithm>
  #include <assert.h>
  #include <cstdlib>
  #include <iostream>
  #include <map>
  #include <set>
  #include <string>
  #include <tuple> 
  #include <unordered_map>
  #include <vector>
  #include <math.h>
  #include <cmath>
  #include <bits/stdc++.h>
  #include <numeric>
  #include <functional>
  
  using namespace std;
  
  // SOLUTION CODE
  // ============================================
  PLACEHOLDER_CODE_BODY
  
  // TESTING CODE 
  // ============================================
  bool validateSolution(int actual, int expected){
      return actual == expected;
  }
  
  string driver(vector<int> arr, int n, int expected){
      try
      {
          if (validateSolution(PLACEHOLDER_FN_NAME(arr, n), expected)){
              return "PASSED";
          }
          return "FAILED";
      }
      catch (const std::overflow_error& exception_obj)
      {
          return typeid(exception_obj).name();
      }
      catch (const std::runtime_error& exception_obj)
      {
          return typeid(exception_obj).name();
      }
      catch (const std::exception& exception_obj)
      {
          return typeid(exception_obj).name();
      }
      catch (...)
      {
          return "UNK_ERROR";
      }
  }
  
  int main() {
      string result = "";
  
      result = driver({4, 5, 7, 12, 23, 31, 31, 45, 47, 60, 67, 70, 84, 85, 91, 96}, 11, 301); 
      cout << "TEST-" << 0 << "..."
           <<  result
           << "\n";
  
      result = driver({-88, -38, -50, -14, 36, -32, 0, -8, -12, -62, -46, 66, -46, -26, 6, -44, 14, -74, -84, 52, -28}, 18, 102); 
      cout << "TEST-" << 1 << "..."
           <<  result
           << "\n";
  
      result = driver({0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}, 39, 1); 
      cout << "TEST-" << 2 << "..."
           <<  result
           << "\n";
  
      result = driver({85, 42, 7, 35, 35, 21, 97, 59, 88, 50, 12, 44, 85, 22, 38, 23, 42, 61, 44, 63, 23, 69, 28, 17, 73, 20, 71, 80, 15, 42, 28, 10, 56, 77, 43}, 26, 396); 
      cout << "TEST-" << 3 << "..."
           <<  result
           << "\n";
  
      result = driver({-92, -82, -82, -74, -72, -68, -68, -66, -60, -54, -42, -38, -36, -32, -30, -16, -14, -12, -10, 14, 24, 28, 34, 34, 38, 42, 44, 52, 70, 72, 80, 84, 86, 94}, 32, 582); 
      cout << "TEST-" << 4 << "..."
           <<  result
           << "\n";
  
      result = driver({0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0}, 8, 1); 
      cout << "TEST-" << 5 << "..."
           <<  result
           << "\n";
  
      result = driver({33}, 0, 0); 
      cout << "TEST-" << 6 << "..."
           <<  result
           << "\n";
  
      result = driver({76, 86, 46, -70, 92, 6, 70, -66, 64, 46, 86, -42, -46, -24, 8, 76, 4, -96, -86, 18, 70, -72, -56, -88, -96, 62, 22, 20, 42}, 21, 254); 
      cout << "TEST-" << 7 << "..."
           <<  result
           << "\n";
  
      result = driver({0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}, 24, 0); 
      cout << "TEST-" << 8 << "..."
           <<  result
           << "\n";
  
      result = driver({25, 46, 41, 61, 93, 29, 65, 24, 10, 89, 22, 51, 18, 65, 70, 59, 87, 82, 97, 99, 15, 64, 20, 97, 12, 23, 76}, 20, 550); 
      cout << "TEST-" << 9 << "..."
           <<  result
           << "\n";
  
      return 0;
  }
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;
  }