## Introduction

In this blog, we will be finding the K-th largest sum Contiguous Subarray. So, let's get started by introducing the array and the subarray.

**An array** is a data structure that can hold a fixed-size sequential collection of the same type of elements. An array is often regarded as a collection of the same type of variables.

The array comes under one of the essential topics for programming interviews, so an individual must have a thorough understanding of this topic.

A **sub-array** is an array with a length less than or equal to the size of the given array, whose elements are all present in the given array.A subarray is a contiguous section of an array

Let us understand the problem statement of K-th Largest Sum Contiguous Subarray

### Problem Statement

Ninja has an array of size N. He gave that array to you. He wants to find the K-th largest sum of contiguous subarray within the array of numbers which can have both negative and positive numbers. But, the problem is that he cannot do it by himself. Can you help him in finding K-th largest sum contiguous subarray?

### Some Examples

**Input:**

`arr[]= {10, 5, -12}, k = 2 `

**Output:**

`10`

Explanation:

All sums of contiguous subarrays are (10, 5, 15, -12, 3,-7), so the 2nd largest sum is 10.

**Input: **

`arr[] = {-1, -6, -8}, k = 3`

**Output: **

`-7`

Explanation:

All sum of contiguous subarrays are (-1, -7, -6, -8, -14,-15), so the 2nd largest sum is -6.

## Brute-Force Approach

We can solve this problem of K-th Largest Sum Contiguous Subarray with a brute force approach by storing sums of all the subarrays in another array, and after that sorting them, and printing the kth largest.

### Implementation in C++

```
#include <bits/stdc++.h>
using namespace std;
vector<int> SumOfAllSubarrays(vector<int> &arr, int n)
{
vector<int> sumArray;
int current = 0;
for (int i = 0; i < n; i++)
{
current = 0;
for (int j = i; j < n; j++)
{
current += arr[j];
sumArray.push_back(current);
}
}
return sumArray;
}
int main()
{
vector<int> arr{3, 5, -1, 9, 8};
int k = 3;
vector<int> ContiguousSumArray = SumOfAllSubarrays(arr, arr.size());
sort(ContiguousSumArray.begin(), ContiguousSumArray.end(), greater<int>());
cout << ContiguousSumArray[k - 1] << endl;
return 0;
}
```

** Output:**

`17`

**Complexity Analysis**

**Time Complexity **

The above approach to solving K-th Largest Sum Contiguous Subarray has a quadratic O((nlog(n))^2) time complexity because we are using nested loops and we are storing all the n^2 sums in the array and after that, we are sorting that array since sorting takes nlog(n) time, therefore, the overall time complexity would be O((nlog(n))^2). Hence, it is not suitable for large input.

**Space Complexity**

We are using an extra array to store the sum of subarrays. The number of subarrays for an array of size N is given by (N * (N + 1) / 2). Hence, the space complexity is O(n). The memory may run out of space since the number of subarrays can be very large**.**

Read More - __Time Complexity of Sorting Algorithms__ and __Rabin Karp Algorithm____.__