title: K Th Largest Sum Contiguous Subarray
signature: k_th_largest_sum_contiguous_subarray <- function(arr, n, k) {
test_code: 
  
  
  # SOLUTION CODE
  # ============================================
  PLACEHOLDER_CODE_BODY
  
  # TESTING CODE 
  # ============================================
  validate_solution <- function(actual, expected) {
      toString(actual)==toString(expected)
  }
  
  driver <- function(arr, n, k, expected){
      if (validate_solution(PLACEHOLDER_FN_NAME(arr, n, k), expected)){
          "PASSED"
      } else{
          "FAILED"
      }
  }
  
  main <- function() {
      cat(sprintf("TEST-0...%s\n",driver(
          list(2L, 3L, 5L, 7L, 8L, 29L, 29L, 44L, 47L, 52L, 60L, 65L, 73L, 83L, 87L, 92L, 92L, 95L), 10L, 12L, 
          157L
      )))
  
      cat(sprintf("TEST-1...%s\n",driver(
          list(44L, -98L, -10L, 14L, -6L, -46L, 6L, -74L, -4L, 36L, 10L, -2L, 30L, 28L, 96L, -84L, -36L, -76L, 64L, -74L, -20L, 94L, -4L, 14L, 78L, 52L, -56L, 98L, -68L, -76L, -10L, 20L, 88L, -98L, 96L, 80L, 96L, -32L, -40L, -30L, 82L), 34L, 37L, 
          166L
      )))
  
      cat(sprintf("TEST-2...%s\n",driver(
          list(0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L), 16L, 15L, 
          5L
      )))
  
      cat(sprintf("TEST-3...%s\n",driver(
          list(58L, 21L, 97L, 78L, 78L, 57L, 29L, 33L, 57L, 81L, 66L, 32L, 11L, 82L, 28L, 72L, 46L, 67L, 42L, 15L, 60L, 45L, 16L, 37L), 14L, 20L, 
          508L
      )))
  
      cat(sprintf("TEST-4...%s\n",driver(
          list(-92L, -90L, -88L, -84L, -68L, -66L, -62L, -58L, -52L, -44L, -22L, -16L, -4L, -4L, 2L, 12L, 14L, 14L, 24L, 26L, 44L, 56L, 80L, 90L, 92L, 94L, 98L), 15L, 25L, 
          -86L
      )))
  
      cat(sprintf("TEST-5...%s\n",driver(
          list(1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 0L, 0L, 0L), 5L, 5L, 
          3L
      )))
  
      cat(sprintf("TEST-6...%s\n",driver(
          list(3L, 4L, 8L, 12L, 13L, 14L, 17L, 19L, 23L, 24L, 28L, 29L, 30L, 35L, 35L, 38L, 44L, 47L, 47L, 53L, 55L, 56L, 56L, 58L, 66L, 67L, 70L, 71L, 72L, 73L, 74L, 75L, 77L, 78L, 82L, 84L, 87L, 87L, 87L, 88L, 88L, 93L, 94L, 96L), 26L, 25L, 
          721L
      )))
  
      cat(sprintf("TEST-7...%s\n",driver(
          list(20L, -58L, 94L, -70L, 18L, 16L, -46L, 38L, -44L, -92L, -20L, -70L, -30L, 50L), 11L, 7L, 
          36L
      )))
  
      cat(sprintf("TEST-8...%s\n",driver(
          list(0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L), 19L, 23L, 
          0L
      )))
  
      cat(sprintf("TEST-9...%s\n",driver(
          list(90L, 77L, 82L, 38L, 96L, 62L, 66L, 4L, 93L, 30L, 75L, 22L, 26L, 61L, 40L, 11L, 38L, 55L, 88L, 24L, 66L, 47L, 40L, 71L, 21L, 5L, 18L, 31L, 26L, 56L, 19L, 47L, 71L, 34L), 28L, 32L, 
          1041L
      )))
  
  }
  
  main()
source_py: def k_th_largest_sum_contiguous_subarray(arr, n, k):
      sum = []
      sum.append(0)
      sum.append(arr[0])
      for i in range(2, (n + 1)):
          sum.append((sum[(i - 1)] + arr[(i - 1)]))
      Q = []
      heapq.heapify(Q)
      for i in range(1, (n + 1)):
          for j in range(i, (n + 1)):
              x = (sum[j] - sum[(i - 1)])
              if (len(Q) < k):
                  heapq.heappush(Q, x)
              elif (Q[0] < x):
                  heapq.heappop(Q)
                  heapq.heappush(Q, x)
      return Q[0]
source_cpp: int k_th_largest_sum_contiguous_subarray(vector<int> arr, int n, int k) {
    int sum [ n + 1 ];
    sum [ 0 ] = 0;
    sum [ 1 ] = arr [ 0 ];
    for ( int i = 2;
    i <= n;
    i ++ ) sum [ i ] = sum [ i - 1 ] + arr [ i - 1 ];
    priority_queue < int, vector < int >, greater < int > > Q;
    for ( int i = 1;
    i <= n;
    i ++ ) {
      for ( int j = i;
      j <= n;
      j ++ ) {
        int x = sum [ j ] - sum [ i - 1 ];
        if ( Q . size ( ) < k ) Q . push ( x );
        else {
          if ( Q . top ( ) < x ) {
            Q . pop ( );
            Q . push ( x );
          }
        }
      }
    }
    return Q . top ( );
  }