## Google Interview Question

**Country:**Canada

**Interview Type:**Written Test

To solve it as stated before we can argue the solutions if the k elements have to be contiguous or not.

Let's start when the elements don't need to be contiguous. The naive solution is is to compute all the possible combinations of k elements and return the maximum sum. The cost for this solution is factorial (from the cost of computing the combinations, computing the sum of k elements is constant).

Code in Python:

```
from itertools import combinations
def getMaxKSum(s, k):
max_sum = 0; numbers = []
for c in combinations(s, k):
r = sum(c)
if r > max_sum:
max_sum = r
numbers = c
return r, numbers
```

We can improve the cost if we sort the array. In this case the cost would be nlogn from the cost of sorting the array. Solution in python

```
def getMaxKSum(s, k):
return sorted(s)[k:]
```

We can improve the cost even further using a heap. For this case the cost is nlogk. Solution in python

```
from heapq import nlargest
def getMaxKSum(s, k):
return nlargest(s, k)
```

If it has to be contiguous we can just create a window of k elements to traverse the array. The cost is linear. Functional solution in python

```
def get_chunks(s, k, step=1):
for x in xrange(0, len(s)-k+step, step):
yield s[x:x+k]
def getMaxKSum(s, k):
return max(map(sum, get_chunks(s, k)))
```

`public static void main(String[] args) {`

`int k = 3;`

`Integer a[] = { 1, 2, 3, 4, 5, 6, 1, 2, 3 };`

`System.out.println("sds");`

`Queue<Integer> queue = new PriorityQueue<>();`

`for (int i = 0; i < k; i++) {`

`queue.add(a[i]);`

`}`

`for (int i = k; i <= a.length - 1; i++) {`

`if (a[i] > queue.peek()) {`

`int remove = queue.poll();`

`queue.add(a[i]);`

`}`

`}`

`System.out.println(queue);`

`}`

`public static void main(String[] args) {`

`int k = 3;`

`Integer a[] = { 1, 2, 3, 4, 5, 6, 1, 2, 3 };`

`System.out.println("sds");`

`Queue<Integer> queue = new PriorityQueue<>();`

`for (int i = 0; i < k; i++) {`

`queue.add(a[i]);`

`}`

`for (int i = k; i <= a.length - 1; i++) {`

`if (a[i] > queue.peek()) {`

`int remove = queue.poll();`

`queue.add(a[i]);`

`}`

`}`

`System.out.println(queue);`

`}`

```
public class MaxSumSubArray {
public static int maxSum(int[] array) {
int maxSoFar = 0;
int maxEndingHere = 0;
for(int i = 0; i < array.length; i++) {
maxEndingHere += array[i];
if (maxSoFar < maxEndingHere) {
maxSoFar = maxEndingHere;
}
if (maxEndingHere < 0) {
maxEndingHere = 0;
}
}
return maxSoFar;
}
public static void main(String[] args) {
int[] array = {4, -1, 5, -5, 1};
System.out.println(maxSum(array));
}
}
```

```
int MaxSubarrayK(vector<int> const &a, int k) {
int max_sum = numeric_limits<int>::min();
if (k > 0 &&
k <= a.size())
{
int head = 0;
int sum = 0;
for (int i = 0; i < a.size(); ++i) {
sum += a[i];
int size = i - head + 1;
if (size >= k) {
if (size > k) {
sum -= a[head++];
}
max_sum = max(max_sum, sum);
}
}
}
return max_sum;
}
```

Does it need to be a contiguous subarray say (1,2,3,4,5,6,1,2,3) k = 3 = (4,5,6) or

- guilhebl June 21, 2017can it be a non-contiguous subarray? say (8,2,3,4,8,6,1,2,8) k = 3 = (8,8,8)

One possible implementation:

if K = N (size of array) return sum of array

else:

if contiguous: (easy case)

Build a subarray of size K starting from (0 ... k)

use 2 vars i and j i = 0, j = k

iterate from i ... n - k

check each element and current sum (removing previous element and adding new one)

return maxSUM

else (if non-contiguous):

use a Min Heap (PriorityQueue) of size K (insert first K elements into it)

iterate from 0 ... N-1

for each a[i] element compare if a[i] > queue.peek() // min element of queue

if greater then: queue.poll // remove min element and queue.add(a[i])

at the end return poll all remaining elements of queue ( Max K elements found )