You are given an array Arr of size N. You have to find the K-th largest sum of contiguous subarray within the array elements.
 
Example 1:
Input:
N = 3
K = 2
Arr = {3,2,1}
Output:
5
Explanation:
The different subarray sums we can get from the array
are = {6,5,3,2,1}. Where 5 is the 2nd largest.
 
Example 2:
Input:
N = 4
K = 3
Arr = {2,6,4,1}
Output:
11
Explanation:
The different subarray sums we can get from the array
are = {13,12,11,10,8,6,5,4,2,1}. Where 11 is the 3rd largest.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function kthLargest() which takes the array Arr[] and its size N as inputs and returns the Kth largest subarray sum.
 
Expected Time Complexity: O(N^{2} * log K)
Expected Auxiliary Space: O(K)
 
Constraints:
1 <= N <= 100
1 <= K <= (N*(N+1))/2
-10^{5} <= Arr[i] <= 10^{5}
Sum of N over all test cases doesn't exceed 1000.
Array may contain duplicate elements.

Difficulty: MEDIUM
Tags: Data structures
Skill types: Data structures
Expected Time Complexity: O(N^{2} * log K)
Expected Auxiliary Space: O(K)

Starter code:
from typing import List





class Solution:

    def kthLargest(self, N : int, K : int, Arr : List[int]) -> int:

        # code here

        



Solutions:
from typing import List
import heapq

class Solution:

	def kthLargest(self, N: int, K: int, Arr: List[int]) -> int:
		res = []
		size = K
		for i in range(N):
			sum = 0
			for j in range(i, N):
				sum = sum + Arr[j]
				if size:
					heapq.heappush(res, sum)
					size = size - 1
				elif res[0] < sum:
					heapq.heappop(res)
					heapq.heappush(res, sum)
		return res[0]


from typing import List

class Solution:

	def kthLargest(self, N: int, K: int, Arr: List[int]) -> int:
		l = []
		for i in range(len(Arr)):
			for j in range(i + 1, len(Arr) + 1):
				s = sum(Arr[i:j])
				l.append(s)
		l = sorted(l)
		t = []
		for i in range(len(l) - 1, -1, -1):
			t.append(l[i])
		return t[K - 1]


from typing import List
import heapq

class Solution:

	def f(self, arr, n, li):
		for i in range(n):
			sum = 0
			for j in range(i, n):
				sum += arr[j]
				li.append(sum)

	def kthLargest(self, N: int, K: int, Arr: List[int]) -> int:
		li = []
		self.f(Arr, N, li)
		heap = []
		for x in li:
			heapq.heappush(heap, -x)
		for i in range(K - 1):
			heapq.heappop(heap)
		return -heapq.heappop(heap)


from typing import List
from heapq import *

class Solution:

	def kthLargest(self, n: int, k: int, arr: List[int]) -> int:
		heap = []
		for i in range(n):
			s = 0
			for j in range(i, n):
				s += arr[j]
				if len(heap) < k:
					heappush(heap, s)
				else:
					top = heap[0]
					if s > top:
						heappop(heap)
						heappush(heap, s)
		return heap[0]


from typing import List
from heapq import *

class Solution:

	def kthLargest(self, n: int, k: int, arr: List[int]) -> int:
		heap = []
		for i in range(n):
			total = 0
			for j in range(i, n):
				total += arr[j]
				if len(heap) < k:
					heappush(heap, total)
				elif total > heap[0]:
					heappop(heap)
					heappush(heap, total)
		return heap[0]


from typing import List

class Solution:

	def kthLargest(self, n: int, k: int, arr: List[int]) -> int:
		store = []
		for i in range(n):
			s = 0
			for j in range(i, n):
				s += arr[j]
				store.append(s)
		store.sort()
		return store[-k]


from typing import List
import heapq

class Solution:

	def kthLargest(self, N: int, K: int, Arr: List[int]) -> int:
		min_heap = []
		for i in range(N):
			summ = 0
			for j in range(i, N):
				summ += Arr[j]
				if len(min_heap) < K:
					heapq.heappush(min_heap, summ)
				elif min_heap[0] < summ:
					heapq.heappop(min_heap)
					heapq.heappush(min_heap, summ)
		return heapq.heappop(min_heap)


from typing import List
import heapq

class Solution:

	def kthLargest(self, N: int, K: int, Arr: List[int]) -> int:
		curr_sum = 0
		list1 = []
		for i in range(0, N - 1):
			curr_sum = 0
			curr_sum = curr_sum + Arr[i]
			list1.append(curr_sum)
			for j in range(i + 1, N):
				curr_sum = curr_sum + Arr[j]
				list1.append(curr_sum)
		list1.append(Arr[N - 1])
		list1.sort(reverse=True)
		return list1[K - 1]


from typing import List

class Solution:

	def kthLargest(self, N: int, K: int, Arr: List[int]) -> int:
		list1 = []
		for i in range(N):
			num = 0
			list1.append(Arr[i])
			num += Arr[i]
			for j in range(i + 1, N):
				num += Arr[j]
				list1.append(num)
		list1.sort()
		return list1[-K]


from typing import List

class Solution:

	def kthLargest(self, N: int, K: int, Arr: List[int]) -> int:
		Sum_arr = []
		for i in range(N):
			Sum = 0
			Sum_arr.append(Arr[i])
			Sum += Arr[i]
			for j in range(i + 1, N):
				Sum += Arr[j]
				Sum_arr.append(Sum)
		Sum_arr.sort(reverse=True)
		return Sum_arr[K - 1]


from typing import List
import heapq as h

class Solution:

	def kthLargest(self, N: int, K: int, Arr: List[int]) -> int:
		minheap = []
		ans = []
		for i in range(N):
			sm = 0
			for j in range(i, N):
				if i == j:
					ans.append(Arr[i])
					sm += Arr[i]
				else:
					sm += Arr[j]
					ans.append(sm)
		for i in ans:
			h.heappush(minheap, -i)
		while K != 1:
			h.heappop(minheap)
			K -= 1
		return -h.heappop(minheap)


from typing import List
import heapq as h

class Solution:

	def kthLargest(self, N: int, K: int, Arr: List[int]) -> int:
		minheap = []
		ans = []
		for i in range(N):
			sm = 0
			for j in range(i, N):
				if i == j:
					ans.append(Arr[i])
					sm += Arr[i]
				else:
					sm += Arr[j]
					ans.append(sm)
		ans.sort(reverse=True)
		return ans[K - 1]


from typing import List
import heapq

class Solution:

	def kthLargest1(self, N: int, K: int, arr: List[int]) -> int:
		sum_arr = []
		for i in range(N):
			summ = arr[i]
			sum_arr.append(summ)
			for j in range(i + 1, N):
				summ += arr[j]
				sum_arr.append(summ)
		sum_arr.sort()
		return sum_arr[-K]

	def kthLargest(self, N: int, K: int, arr: List[int]) -> int:
		min_heap = []
		for i in range(N):
			summ = 0
			for j in range(i, N):
				summ += arr[j]
				if len(min_heap) < K:
					heapq.heappush(min_heap, summ)
				elif min_heap[0] < summ:
					heapq.heappop(min_heap)
					heapq.heappush(min_heap, summ)
		return heapq.heappop(min_heap)


from typing import List

class Solution:

	def kthLargest(self, N: int, K: int, arr: List[int]) -> int:
		sum_arr = []
		for i in range(N):
			summ = arr[i]
			sum_arr.append(summ)
			for j in range(i + 1, N):
				summ += arr[j]
				sum_arr.append(summ)
		sum_arr.sort()
		return sum_arr[-K]


from typing import List
from queue import PriorityQueue

def kth_largest_contiguous_sub_arr(input_arr: [], n, k: int):
	data_queue = PriorityQueue()
	sum_arr = [input_arr[0]]
	for i in range(1, n):
		sum_arr.append(sum_arr[i - 1] + input_arr[i])
	for i in range(n):
		for j in range(i, n):
			if i == 0:
				sum_value = sum_arr[j]
			else:
				sum_value = sum_arr[j] - sum_arr[i - 1]
			if len(data_queue.queue) < k:
				data_queue.put(sum_value)
			else:
				min_element = data_queue.get()
				if min_element < sum_value:
					data_queue.put(sum_value)
				else:
					data_queue.put(min_element)
	return data_queue.get()

class Solution:

	def kthLargest(self, N: int, K: int, Arr: List[int]) -> int:
		return kth_largest_contiguous_sub_arr(Arr, N, K)


from typing import List
from heapq import heappush, heapreplace

class Solution:

	def kthLargest(self, N: int, K: int, Arr: List[int]) -> int:
		heap = []
		for i in range(N):
			cur = 0
			for j in range(i, N):
				cur += Arr[j]
				if len(heap) < K:
					heappush(heap, cur)
				elif heap[0] < cur:
					heapreplace(heap, cur)
		return heap[0]


from typing import List

class Solution:

	def kthLargest(self, N: int, K: int, Arr: List[int]) -> int:
		sumArray = []
		for i in range(0, N):
			sum = 0
			for j in range(i, N):
				sum += Arr[j]
				sumArray.append(sum)
		sumArray.sort()
		return sumArray[len(sumArray) - K]


from typing import List
import heapq as hq

class Solution:

	def kthLargest(self, N: int, K: int, Arr: List[int]) -> int:
		h = []
		summ = 0
		hq.heapify(h)
		for i in range(N):
			summ = 0
			for j in range(i, N):
				summ += Arr[j]
				if len(h) == K:
					if summ > h[0]:
						hq.heappushpop(h, summ)
				else:
					hq.heappush(h, summ)
		return h[0]


from typing import List
import bisect

class Solution:

	def kthLargest(self, N: int, K: int, arr: List[int]) -> int:
		l = []
		for i in range(N):
			for j in range(i, N):
				s = sum(arr[i:j + 1])
				bisect.insort(l, s)
		return l[-K]


from typing import List

class Solution:

	def kthLargest(self, N: int, K: int, Arr: List[int]) -> int:
		temp = []
		for i in range(N):
			count = 0
			for j in range(i, N):
				count += Arr[j]
				temp.append(count)
		temp.sort(reverse=True)
		if len(temp) < K - 1:
			return -1
		else:
			return temp[K - 1]


from typing import List
import heapq

class Solution:

	def kthLargest(self, N: int, K: int, Arr: List[int]) -> int:
		ans = []
		for i in range(N):
			sm = 0
			for j in range(i, N):
				sm = sm + Arr[j]
				ans.append(sm)
		heapq._heapify_max(ans)
		ans2 = heapq.nlargest(K, ans)
		return ans2[-1]


from typing import List

class Solution:

	def kthLargest(self, N: int, K: int, Arr: List[int]) -> int:
		subarr = []
		for i in range(N):
			ans = 0
			for j in range(i, N):
				ans += Arr[j]
				subarr.append(ans)
		subarr.sort()
		subarr.reverse()
		return subarr[K - 1]


from typing import List
from heapq import *

class Solution:

	def kthLargest(self, N: int, K: int, Arr: List[int]) -> int:
		ans = []
		for i in range(N):
			sum1 = 0
			for j in range(i, N):
				sum1 += Arr[j]
				ans.append(sum1)
		minheap = []
		for i in range(len(ans)):
			heappush(minheap, ans[i])
			if len(minheap) == K + 1:
				heappop(minheap)
		res = []
		while minheap:
			res.append(heappop(minheap))
		return res[0]


from typing import List

class Solution:

	def kthLargest(self, n: int, K: int, Arr: List[int]) -> int:

		def heapify(arr, n, i):
			(temp, left, right) = (i, 2 * i + 1, 2 * i + 2)
			if left < n and arr[left] > arr[temp]:
				temp = left
			if right < n and arr[right] > arr[temp]:
				temp = right
			if temp != i:
				(arr[i], arr[temp]) = (arr[temp], arr[i])
				heapify(arr, n, temp)

		def buildheap(arr, n):
			for i in range(n // 2 - 1, -1, -1):
				heapify(arr, n, i)
		ans = []
		for i in range(n):
			summ = Arr[i]
			ans.append(summ)
			for j in range(i + 1, n):
				summ += Arr[j]
				ans.append(summ)
		x = len(ans)
		buildheap(ans, x)
		k = 0
		if K == 1:
			return ans[0]
		for i in range(x - 1, -1, -1):
			(ans[0], ans[i]) = (ans[i], ans[0])
			heapify(ans, i, 0)
			k += 1
			if k == K - 1:
				break
		return ans[0]


from typing import List
import heapq as hq

class Solution:

	def kthLargest(self, n: int, k: int, Arr: List[int]) -> int:
		min_heap = []
		for i in range(n):
			sum = 0
			for j in range(i, n):
				sum += Arr[j]
				hq.heappush(min_heap, sum)
				if len(min_heap) > k:
					hq.heappop(min_heap)
		return min_heap[0]


from typing import List

class Solution:

	def kthLargest(self, N: int, K: int, Arr: List[int]) -> int:
		arr = Arr
		from heapq import heappush, heappop
		min_heap = []
		for i in range(N):
			sum = 0
			for j in range(i, N):
				sum += arr[j]
				heappush(min_heap, -sum)
		for i in range(1, K):
			heappop(min_heap)
		return -min_heap[0]


from typing import List

class Heap:

	def __init__(self, k):
		self.heap = [0] * k
		self.size = k
		self.current = 0

	def left(self, i):
		return i * 2 + 1

	def right(self, i):
		return 2 * i + 2

	def parent(self, i):
		return (i - 1) // 2

	def append(self, ele):
		self.heap[self.current] = ele
		i = self.current
		parent = self.parent(i)
		self.current += 1
		while i > 0 and self.heap[parent] > self.heap[i]:
			(self.heap[parent], self.heap[i]) = (self.heap[i], self.heap[parent])
			i = parent
			parent = self.parent(i)

	def heapify(self, i):
		smallest = i
		left = self.left(i)
		right = self.right(i)
		if left < self.current and self.heap[smallest] > self.heap[left]:
			smallest = left
		if right < self.current and self.heap[smallest] > self.heap[right]:
			smallest = right
		if i != smallest:
			(self.heap[smallest], self.heap[i]) = (self.heap[i], self.heap[smallest])
			self.heapify(smallest)

	def update(self, ele):
		self.heap[0] = ele
		self.heapify(0)

	def get_min(self):
		return self.heap[0]

class Solution:

	def kthLargest(self, n: int, k: int, arr: List[int]) -> int:
		heap = Heap(k)
		for i in range(n):
			sm = 0
			for j in range(i, n):
				sm += arr[j]
				if k != 0:
					heap.append(sm)
					k -= 1
				elif sm > heap.get_min():
					heap.update(sm)
		return heap.get_min()


from typing import List

class Solution:

	def kthLargest(self, N: int, K: int, Arr: List[int]) -> int:
		l = []
		for i in range(len(Arr)):
			s = 0
			for j in range(i, len(Arr)):
				s += Arr[j]
				l.append(s)
		l = sorted(l, reverse=True)
		return l[K - 1]


from typing import List
import heapq

class Solution:

	def kthLargest(self, N: int, K: int, arr: List[int]) -> int:

		def add(kth, k, ele):
			if len(kth) < k:
				heapq.heappush(kth, ele)
			elif kth[0] < ele:
				heapq.heappushpop(kth, ele)
		kth = []
		for i in range(N):
			cur_sum = 0
			for j in range(i, N):
				cur_sum += arr[j]
				add(kth, K, cur_sum)
		return kth[0]


from typing import List

class Solution:

	def kthLargest(self, N: int, K: int, Arr: List[int]) -> int:
		min_heap = []
		prefix_sum = [0] * N
		sum = 0
		import heapq
		for i in range(N):
			sum += Arr[i]
			prefix_sum[i] = sum
		for i in range(N):
			for j in range(i, N):
				if i != 0:
					sum = prefix_sum[j] - prefix_sum[i - 1]
				else:
					sum = prefix_sum[j]
				if len(min_heap) < K:
					heapq.heappush(min_heap, sum)
				elif min_heap[0] < sum:
					heapq.heapreplace(min_heap, sum)
		return min_heap[0]


from typing import List
import heapq

class Solution:

	def kthLargest(self, N: int, k: int, arr: List[int]) -> int:
		n = len(arr)
		sums = []
		for i in range(n):
			for j in range(i + 1, n + 1):
				sums.append(sum(arr[i:j]))
		heap = heapq.nlargest(k, sums)
		return heap[-1]


from typing import List
import heapq

class Solution:

	def kthLargest(self, N: int, k: int, arr: List[int]) -> int:
		heap = []
		for i in range(len(arr)):
			curr_sum = 0
			for j in range(i, len(arr)):
				curr_sum += arr[j]
				if len(heap) < k:
					heapq.heappush(heap, curr_sum)
				elif curr_sum > heap[0]:
					heapq.heapreplace(heap, curr_sum)
		return heap[0]


from typing import List

class Solution:

	def kthLargest(self, N: int, K: int, Arr: List[int]) -> int:
		import heapq
		fin = []
		for i in range(N):
			s = 0
			for j in range(i, N):
				s = s + Arr[j]
				heapq.heappush(fin, s)
				if len(fin) > K:
					heapq.heappop(fin)
		return fin[0]


from typing import List
import heapq

class Solution:

	def kthLargest(self, N: int, k: int, arr: List[int]) -> int:
		minheap = []
		n = len(arr)
		l = []
		for i in range(n):
			sum_ = 0
			for j in range(i, n):
				sum_ += arr[j]
				if len(minheap) < k:
					minheap.append(sum_)
				else:
					heapq.heapify(minheap)
					if sum_ > minheap[0]:
						heapq.heappop(minheap)
						heapq.heappush(minheap, sum_)
		heapq.heapify(minheap)
		return minheap[0]


from typing import List

class Solution:

	def kthLargest(self, N: int, k: int, arr: List[int]) -> int:
		n = len(arr)
		l = []
		for i in range(n):
			sum_ = 0
			for j in range(i, n):
				sum_ += arr[j]
				l.append(sum_)
		l[:] = sorted(l)
		return l[len(l) - k]


from typing import List

class Solution:

	def kthLargest(self, N: int, K: int, Arr: List[int]) -> int:
		new_lst = []
		for i in range(N):
			new_lst.append(Arr[i])
			for j in range(i + 1, N):
				new_lst.append(sum(Arr[i:j + 1]))
		sort_lst = sorted(new_lst, reverse=True)
		return sort_lst[K - 1]


from typing import List

class Solution:

	def kthLargest(self, N: int, K: int, Arr: List[int]) -> int:
		ans = []
		for i in range(N):
			for j in range(i + 1, N + 1):
				s = sum(Arr[i:j])
				ans.append(s)
		ans.sort()
		return ans[len(ans) - K]


from typing import List
import heapq

class Solution:

	def kthLargest(self, N: int, k: int, Arr: List[int]) -> int:
		ansarr = []
		for i in range(N):
			temp = 0
			for j in range(i, N):
				temp += Arr[j]
				if len(ansarr) < k:
					heapq.heappush(ansarr, temp)
				elif temp > ansarr[0]:
					heapq.heappop(ansarr)
					heapq.heappush(ansarr, temp)
		return ansarr[0]


from typing import List

class Solution:

	def kthLargest(self, N: int, k: int, Arr: List[int]) -> int:
		ansarr = []
		for i in range(N):
			temp = Arr[i]
			ansarr.append(Arr[i])
			for j in range(i + 1, N):
				temp += Arr[j]
				ansarr.append(temp)
		ansarr.sort()
		return ansarr[-k]


from typing import List

class Solution:

	def kthLargest(self, N: int, K: int, Arr: List[int]) -> int:
		l = []
		for i in range(N):
			k = Arr[i]
			l.append(k)
			for j in range(i + 1, N):
				k += Arr[j]
				l.append(k)
		l.sort()
		return l[::-1][K - 1]


from typing import List

class Solution:

	def kthLargest(self, N: int, K: int, arr: List[int]) -> int:
		res = []
		n = len(arr)
		for i in range(n):
			sum = 0
			for j in range(i, n):
				sum += arr[j]
				res.append(sum)
		res.sort(reverse=True)
		return res[K - 1]


from typing import List

class Solution:

	def kthLargest(self, N: int, K: int, Arr: List[int]) -> int:
		res = []
		for x in range(N):
			sum = 0
			for y in range(x, N):
				sum += Arr[y]
				res.append(sum)
		res.sort(reverse=True)
		return res[K - 1]


from typing import List

class Solution:

	def kthLargest(self, N: int, K: int, Arr: List[int]) -> int:
		res = []
		for i in range(N):
			tmp = 0
			for j in range(i, N):
				tmp += Arr[j]
				res.append(tmp)
		res.sort()
		return res[-K]


from typing import List
import heapq

class Solution:

	def kthLargest(self, N: int, K: int, Arr: List[int]) -> int:
		ls = []
		for i in range(N):
			curr = 0
			for j in range(i, N):
				curr += Arr[j]
				ls.append(curr)
		ls.sort()
		size = N * (N + 1) // 2
		return ls[size - K]


from typing import List
import heapq

class Solution:

	def kthLargest(self, n: int, K: int, Arr: List[int]) -> int:
		h = []
		heapq.heapify(h)
		for i in range(n):
			sum1 = 0
			for j in range(i, n):
				sum1 += Arr[j]
				if len(h) < K:
					heapq.heappush(h, sum1)
				elif sum1 > h[0]:
					heapq.heappop(h)
					heapq.heappush(h, sum1)
		return h[0]


from typing import List

class Solution:

	def kthLargest(self, n: int, K: int, Arr: List[int]) -> int:
		arr = []
		for i in range(n):
			sum1 = 0
			for j in range(i, n):
				sum1 += Arr[j]
				arr.append(sum1)
		arr.sort()
		return arr[len(arr) - K]


from typing import List

class Solution:

	def kthLargest(self, N: int, k: int, arr: List[int]) -> int:
		heap = []
		sum1 = 0
		ans = []
		import heapq
		for i in range(len(arr)):
			sum1 = 0
			for j in range(i, len(arr)):
				sum1 += arr[j]
				heapq.heappush(heap, sum1)
				k -= 1
				if k < 0:
					heapq.heappop(heap)
		return heap[0]


from typing import List
import heapq

class Solution:

	def kthLargest(self, N: int, K: int, Arr: List[int]) -> int:
		Arr = [0] + Arr
		for i in range(1, N + 1):
			Arr[i] += Arr[i - 1]
		heap = []
		for i in range(1, N + 1):
			for j in range(i, N + 1):
				sum = Arr[j] - Arr[i - 1]
				heapq.heappush(heap, sum)
				if len(heap) > K:
					heapq.heappop(heap)
		return heap[0]


from typing import List
import heapq

class Solution:

	def kthLargest(self, n: int, k: int, a: List[int]) -> int:
		minhp = []
		for i in range(n):
			csum = 0
			for j in range(i, n):
				csum += a[j]
				heapq.heappush(minhp, csum)
				if len(minhp) > k:
					heapq.heappop(minhp)
		return minhp[0]


from typing import List
import heapq

class Solution:

	def kthLargest(self, N: int, K: int, arr: List[int]) -> int:
		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]


from typing import List
from heapq import heappush, heappop

class Solution:

	def kthLargest(self, N: int, k: int, arr: List[int]) -> int:
		heap = []
		count = 0
		for i in range(N):
			temp = 0
			for j in range(i, N):
				temp += arr[j]
				count += 1
				if count <= k:
					heappush(heap, temp)
				if count > k and temp > heap[0]:
					heappop(heap)
					heappush(heap, temp)
		return heap[0]


from typing import List

class Solution:

	def kthLargest(self, N: int, K: int, Arr: List[int]) -> int:
		res = []
		for i in range(N):
			summ = Arr[i]
			res.append(summ)
			for j in range(i + 1, N):
				summ += Arr[j]
				res.append(summ)
		res.sort(reverse=True)
		return res[K - 1]


from typing import List
import heapq

class Solution:

	def solve(self, nums, k):
		l = 0
		r = 0
		sum_ = 0
		while r < len(nums):
			sum_ += nums[r]
			r += 1
			if r - l == k:
				heapq.heappush(self.heap, sum_)
				sum_ -= nums[l]
				l += 1
				if len(self.heap) > self.k:
					heapq.heappop(self.heap)
		return

	def kthLargest(self, N: int, K: int, Arr: List[int]) -> int:
		self.k = K
		self.heap = []
		for n in range(1, N + 1):
			self.solve(Arr, n)
		return self.heap[0]


from typing import List
from heapq import heappop, heapify, heappush

class Solution:

	def kthLargest(self, N: int, K: int, Arr: List[int]) -> int:
		heap = []
		heapify(heap)
		for i in range(len(Arr)):
			sum_ = 0
			for j in range(i, len(Arr)):
				sum_ = sum_ + Arr[j]
				if len(heap) < K:
					heappush(heap, sum_)
				elif heap[0] < sum_:
					heappop(heap)
					heappush(heap, sum_)
		return heap[0]


from typing import List
import heapq

class Solution:

	def kthLargest(self, N: int, k: int, arr: List[int]) -> int:
		res = []
		for i in range(N):
			sumv = 0
			for j in range(i, N):
				sumv += arr[j]
				if len(res) < k:
					heapq.heappush(res, sumv)
				elif res[0] < sumv:
					heapq.heappop(res)
					heapq.heappush(res, sumv)
		return res[0]


from typing import List

class Solution:

	def kthLargest(self, n: int, k: int, arr: List[int]) -> int:
		s = []
		j = 0
		for i in range(n):
			a = 0
			s.append(arr[i])
			for j in range(i + 1, n):
				a += arr[j]
				s.append(arr[i] + a)
		s.sort(reverse=True)
		return s[k - 1]


from typing import List
import heapq

class Solution:

	def kthLargest(self, N: int, K: int, Arr: List[int]) -> int:
		l = []
		heapq.heapify(l)
		for j in range(N):
			sum = 0
			for i in range(j, N):
				sum += Arr[i]
				if len(l) < K:
					heapq.heappush(l, sum)
				else:
					a = heapq.heappop(l)
					if a < sum:
						heapq.heappush(l, sum)
					else:
						heapq.heappush(l, a)
		return l[0]


import heapq
from typing import List

class Solution:

	def kthLargest(self, N: int, K: int, Arr: List[int]) -> int:
		heap = []
		Arr = [-i for i in Arr]
		for i in range(N):
			csum = 0
			for j in range(i, N):
				csum += Arr[j]
				heapq.heappush(heap, csum)
		while K:
			res = heapq.heappop(heap)
			K -= 1
		return -res