Given an array, find the subarray (containing at least k numbers) which has the largest sum.
Examples:
Input : arr[] = {-4, -2, 1, -3}
k = 2
Output : -1
The sub array is {-2, 1}
Input : arr[] = {1, 1, 1, 1, 1, 1}
k = 2
Output : 6
The sub array is {1, 1, 1, 1, 1, 1}
publicclassSolution {publicintmaxSumWithK(int a[],int n,int k) {// maxSum[i] is going to store maximum sum// till index i such that a[i] is part of the sum.int maxSum[] =newint[n]; maxSum[0] = a[0];// We use Kadane's algorithm to fill maxSum[]int curr_max = a[0];for (int i =1; i < n; i++) { curr_max =Math.max(a[i], curr_max + a[i]); maxSum[i] = curr_max; }// Sum of first k elementsint sum =0;for (int i =0; i < k; i++) sum += a[i];// Use the concept of sliding windowint result = sum;for (int i = k; i < n; i++) { sum = sum + a[i] - a[i - k]; result =Math.max(result, sum);// Include maximum sum till [i-k] also// if it increases overall max. result =Math.max(result, sum + maxSum[i - k]); }return result; }}