title: Dynamic Programming Set 14 Maximum Sum Increasing Subsequence
signature: fun dynamicProgrammingSet14MaximumSumIncreasingSubsequence(arr: ArrayList<Int>, n: Int): Int {
test_code: package main
  
  import kotlin.text.*
  import kotlin.math.*
  
  
  // SOLUTION CODE
  // ===================================
  PLACEHOLDER_CODE_BODY
  
  // TESTING CODE
  // ===================================
  fun validateSolution(actual:Int, expected:Int):Boolean{
    return actual.equals(expected)
  }
  fun driver(arr: ArrayList<Int>, n: Int, expected:Int):String {
      try{
        if (validateSolution(PLACEHOLDER_FN_NAME(arr, n), expected)) {
                return "PASSED"
        }
        return "FAILED"
      } catch (e: Exception){
        return e::class.simpleName as String
      }
  
  }
  
  fun main() {
      var result: String = ""
      result = driver(arrayListOf(4, 5, 7, 12, 23, 31, 31, 45, 47, 60, 67, 70, 84, 85, 91, 96), 11, 301)
      println("TEST-0...${result}")
      
      result = driver(arrayListOf(-88, -38, -50, -14, 36, -32, 0, -8, -12, -62, -46, 66, -46, -26, 6, -44, 14, -74, -84, 52, -28), 18, 102)
      println("TEST-1...${result}")
      
      result = driver(arrayListOf(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)
      println("TEST-2...${result}")
      
      result = driver(arrayListOf(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)
      println("TEST-3...${result}")
      
      result = driver(arrayListOf(-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)
      println("TEST-4...${result}")
      
      result = driver(arrayListOf(0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0), 8, 1)
      println("TEST-5...${result}")
      
      result = driver(arrayListOf(33), 0, 0)
      println("TEST-6...${result}")
      
      result = driver(arrayListOf(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)
      println("TEST-7...${result}")
      
      result = driver(arrayListOf(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)
      println("TEST-8...${result}")
      
      result = driver(arrayListOf(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)
      println("TEST-9...${result}")
      
          
  }
  
  main()
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;
  }