Finding K-size sub array with minimum sum

Problem solving with programming: Finding K-size sub array with minimum sum

Given an array of size N and a number K. We have to find the sub-array of size K such that the sum of it's elements is minimum among all K-size sub arrays.

For example Let us consider the following array of size 10. 

{1, 2, 1, 3, 1, 1, 1, 4, 2, 3}

The smallest sub-array of size 3 is {1, 1, 1} which starts at the index 4 (0-based index).

We can use the following algorithm.

We calculate the sum of first K numbers initially and assume that this is the minimum sum and the index is 0. We maintain a variable to track the running sum of K values.

When we move the sliding window by one element, we subtract the previous element add the current element to the running sum. Then we update the minimum sum if the latest sum is less than minimum sum.

This procedure is repeated till the sliding window reaches the end of the array.

	int n, k; cin >> n >> k;
	int * array = new int[n];
	int i;
	for( i = 0; i < n; i++ )
	{
	cin >> array[i];
	}
	//calculate the sum of first K numbers
	long kSum = 0;
	for ( i = 0; i < k; i++ )
	{
	kSum += array[i];
	}
	//init minimum sum and it's index
	long minSum = kSum;
	int resultInd = 0;
	//start sliding window from index 1; it goes up to n-k
	int start = 1;
	while ( start <= n-k )
	{
	//subtract previous and add current element
	kSum = kSum - array[start-1] + array[i];
	if( kSum < minSum )
	{
	minSum = kSum;
	resultInd = start;
	}
	i++;
	start++;
	}
	cout << resultInd << endl

Read full article from Problem solving with programming: Finding K-size sub array with minimum sum