title: Dynamic Programming Set 14 Maximum Sum Increasing Subsequence
signature: func dynamicProgrammingSet14MaximumSumIncreasingSubsequence(arr []int, n int) int {
test_code: package main
  
  import (
      "fmt"
      "reflect"
      "math"
      "sort"
  )
  
  // SOLUTION CODE
  // ===================================
  PLACEHOLDER_CODE_BODY
  
  // TESTING CODE
  // ===================================
  func validateSolution(actual int, expected int) bool {
      return reflect.DeepEqual(actual,expected)
  }
  
  func driver(arr []int, n int, expected int) string {
      if validateSolution(PLACEHOLDER_FN_NAME(arr, n),expected) {
              return "PASSED"
      }
      return "FAILED"
  
  }
  
  func main() {
  
      // Use imports to avoid undefined errors
      var _ = reflect.DeepEqual
      _ = math.Abs
      _ = sort.Sort
      result := ""
      result = driver([]int{4, 5, 7, 12, 23, 31, 31, 45, 47, 60, 67, 70, 84, 85, 91, 96}, 
  	11, 301)
      fmt.Printf("TEST-0...%s\n", result)
      
      result = driver([]int{-88, -38, -50, -14, 36, -32, 0, -8, -12, -62, -46, 66, -46, -26, 6, -44, 14, -74, -84, 52, -28}, 
  	18, 102)
      fmt.Printf("TEST-1...%s\n", result)
      
      result = driver([]int{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)
      fmt.Printf("TEST-2...%s\n", result)
      
      result = driver([]int{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)
      fmt.Printf("TEST-3...%s\n", result)
      
      result = driver([]int{-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)
      fmt.Printf("TEST-4...%s\n", result)
      
      result = driver([]int{0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0}, 
  	8, 1)
      fmt.Printf("TEST-5...%s\n", result)
      
      result = driver([]int{33}, 
  	0, 0)
      fmt.Printf("TEST-6...%s\n", result)
      
      result = driver([]int{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)
      fmt.Printf("TEST-7...%s\n", result)
      
      result = driver([]int{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)
      fmt.Printf("TEST-8...%s\n", result)
      
      result = driver([]int{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)
      fmt.Printf("TEST-9...%s\n", result)
      
          
  }
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;
  }