Largest sum subarray with at-least k numbers

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}
public class Solution {
    public int maxSumWithK(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[] = new int[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 elements
        int sum = 0;
        for (int i = 0; i < k; i++)
            sum += a[i];

        // Use the concept of sliding window
        int 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;
    }
}

Last updated