Finding maximum sum of a subarray of given size k.

+1 vote
asked in Interview Question by nitin2604
edited by nitin2604

Find the maximum sum of the subarray of given size k.

Example –>

Take value of K = 5

Input value = “31, 1, 2, 21, 44, 31, 10, 17, 0”

Output Value = “ 123 ”

 

 

Add question to:
commented by shivani
What is value of k in your example?
commented by nitin2604
Sorry its 5. You, can  check now..

1 Answer

+2 votes
answered by nitin2604
selected by admin
 
Best answer

Find maximum sum of a subarray, of given size k. Concept to solve this problem is by using a “ Sliding Window ” . 

Steps:

  1. Calculate the sum of first k elements of the array (consider this a subarray window of size k).
  2.  Now, move the window by adding next array element and remove first element of window(subarray).

Kindly see the code for more clarity.

Example: 31, 1, 2, 21, 44, 31, 10, 17, 0

K = 5

Step 1 → 31, 1, 2, 21, 44, 31, 10, 17, 0 

temp = 99 //temp = addding up all element till k = 5

Step 2 → 31, 1, 2, 21, 44, 31, 10, 17, 0

temp = 99 ,

current_value += input_array[j] - input_array[j - k_value];

Current value = 99

temp = max(current_value, temp);

temp = max(99,99)

Step 3 → 31, 1, 2, 21, 44, 31, 10, 17, 0

temp = 99

current value = 108

temp =max(108,99)..


//sliding Window Method
//input array {31, 1, 2, 21, 44, 31, 10, 17, 0}
//expected output "123"
//k value = 5;
#include "iostream"
#include "algorithm"
using namespace std;

int sliding_window(int *input_array, int k_value, int inp_arr_size){
	//checking condition if size is of the array is less than k_value
	if (k_value > inp_arr_size){
		cout << " invalid k value" << endl;
		exit (0);
	}
	//calculate sum for first k value;
	int temp = 0, current_value;
	for (size_t i = 0; i < k_value; i++)
		temp += input_array[i];

	current_value = temp;
	for (size_t j = k_value; j < inp_arr_size; j++)
	{
		current_value += input_array[j] - input_array[j - k_value];
		temp = max(current_value, temp);
	}
	return temp;
}

int main(){
	int input_array[] = { 31, 1, 2, 21, 44, 31, 10, 17, 0 };
	int inp_arr_size = sizeof(input_array) / sizeof(input_array[0]);
	int k_value = 5;
	cout <<" Output " << sliding_window(input_array, k_value, inp_arr_size) << endl;
	return 0;
}

 

commented by shivani
@nitin2604, As I already told you that your logics are super but your English is so pathetic that it is ruining all your efforts.Please read this solution again and try to improve it as well as your English.
commented by nitin2604
Hey, i m trying to bring more clarity on my explanation part.... thanx for the guidance.. (y)
commented by shivani
It is 'thanks' not thanx :P. Better  you install Grammarly extension on your browser, It helps alot.
...