CareerCup

Does it need to be a contiguous subarray say (1,2,3,4,5,6,1,2,3) k = 3 = (4,5,6) or
can 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 )

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));
    }
}

For the non contiguous part, I think the largest sum would be of the largest k elements in the array. Just use sorting or heap data structure to solve.

Non-contiguous subarrays are usually referred to as Subsequences.

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;
}