> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/dynamic-programming/largest-sum-subarray-with-at-least-k-numbers.md).

# 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}
```

```java
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;
    }
}
```