# Largest Sum Subarray Of Size k.

**Given an array , we need to find the largest sum subarray of size k.
**

(Note: )

**Method 1 :
**

We use 2 loops.

Outer loop iterates over the entire array.

Inner loop starts with position of outer loop and calculates the sum of next k elements.

Sum is compared with the max_sum.

**This method has a time complexity of O(n^n).**

#include <stdio.h> int main(void) { // your code goes here int arr[] = {2,5,1,3,7,1,3,4,9,1}; int k = 4; int size = sizeof(arr)/sizeof(int); int i,j,sum,max = -1000; for(i=0;i<size-k;i++){ sum = 0; for(j=i;j<i+k;j++){ sum += arr[j]; } if(sum>max) max = sum; } printf("%d\n",max); return 0; }

Better Solution :

We calculate sum array as : sum[i] = sum[i-1] + arr[i] (where sum[0] = arr[0])

This takes time O(n).

Now to calculate sum between any 2 index take constant time.

Suppose I need to find sum of subarray from index 2 to 5

=> sum[5] – sum[1]

Now we can calculate sum of all subarrays of size k and find the maximum in time O(n)

**This method has time complexity of O(n)**

#include <stdio.h> #define MAX 1000 int main(void) { // your code goes here int arr[] = {2,5,1,3,7,1,3,4,9,1}; int k = 4; int size = sizeof(arr)/sizeof(int); int sum[MAX],i; sum[0] = arr[0]; for(i=1;i<size;i++){ sum[i] = sum[i-1] + arr[i]; } int max = sum[k-1]; for(i=k+1;i<size;i++){ //Checking between i & i-k if((sum[i]-sum[i-k])>max){ max = sum[i]-sum[i-k]; } } printf("%d\n",max); return 0; }