Maximum Sum of K Consecutive Elements in a Circular Array Using Sliding Window in Java

Problem Statement

We are given:

An array arr[] containing the fruit values of trees.

The trees are arranged in a circle, so the first and last trees are also neighbors.

An integer m, representing the maximum number of trees the bird can visit.

The bird can start at any tree and move to neighboring trees. We need to find the maximum total fruit value the bird can collect by visiting at most m trees.

Example

arr = [2, 1, 3, 5, 0, 1, 4]
m = 3

The best choice is:

1 + 3 + 5 = 9

Therefore:

Answer = 9

Key Observation

Since the trees are arranged in a circle, the bird always visits consecutive trees.

For example:

[2, 1, 3, 5, 0, 1, 4]

If m = 3, possible groups include:

2, 1, 3
1, 3, 5
3, 5, 0
5, 0, 1
0, 1, 4
1, 4, 2 ← circular
4, 2, 1 ← circular

So the problem becomes:

Find the maximum sum of m consecutive elements in a circular array.

Because every fruit value is non-negative, using the maximum allowed number of trees is always optimal. Therefore, we use:

k = Math.min(m, n);

If m > n, the bird cannot visit more than n distinct trees, so we consider the entire array.

Sliding Window Technique

A brute-force solution would calculate the sum of every possible group of m trees.

That could take:

O(n × m)

which is too slow when n and m can be as large as 10^6.

Instead, we use a sliding window.

Suppose:

arr = [2, 1, 3, 5, 0, 1, 4]
m = 3

First calculate:

2 + 1 + 3 = 6

Now move the window one position:

[2, 1, 3] → [1, 3, 5]

Instead of calculating 1 + 3 + 5 from scratch:

old sum = 6
remove 2
add 5
new sum = 6 - 2 + 5
= 9

This takes constant time.

Handling the Circular Array

This is the most important part of the problem.

Consider:

arr = [7, 2, 1, 3, 4]

For m = 2, the normal windows are:

But because the array is circular, we also need:

4 + 7

We can handle this without creating another array.

We use:

i % n

For example, if:

n = 5

then:

0 % 5 = 0
1 % 5 = 1
2 % 5 = 2
3 % 5 = 3
4 % 5 = 4
5 % 5 = 0
6 % 5 = 1

So after reaching the last element, % n automatically takes us back to the beginning.

Complete Java Code

import java.util.*;

class Solution {
    public int maxFruits(ArrayList<Integer> arr, int m) {
        int n = arr.size();

        // We cannot visit more than n trees
        int k = Math.min(m, n);

        // Calculate the first window
        int windowSum = 0;

        for (int i = 0; i < k; i++) {
            windowSum += arr.get(i);
        }

        int maxSum = windowSum;

        // Slide the window around the circular array
        for (int i = k; i < n + k - 1; i++) {
            // Remove the element leaving the window
            windowSum -= arr.get((i - k) % n);

            // Add the new element entering the window
            windowSum += arr.get(i % n);

            maxSum = Math.max(maxSum, windowSum);
        }

        return maxSum;
    }
}

Line-by-Line Explanation

1. Get the Array Size

int n = arr.size();

If:

arr = [2, 1, 3, 5, 0, 1, 4]

then:

n = 7

2. Determine the Window Size

int k = Math.min(m, n);

Suppose:

n = 7
m = 3

then:

k = 3

If:

n = 7
m = 10

then:

k = 7

because there are only 7 trees.

3. Calculate the First Window

int windowSum = 0;

for (int i = 0; i < k; i++) {
    windowSum += arr.get(i);
}

For:

arr = [2, 1, 3, 5, 0, 1, 4]
k = 3

we calculate:

2 + 1 + 3 = 6

So:

windowSum = 6

4. Store the Maximum

int maxSum = windowSum;

Initially:

maxSum = 6

5. Slide the Window

for (int i = k; i < n + k - 1; i++)

This allows us to check all possible circular windows.

For each new window, two things happen:

windowSum -= arr.get((i - k) % n);

Remove the old element.

Then:

windowSum += arr.get(i % n);

Add the new element.

Dry Run

Let's use:

arr = [2, 1, 3, 5, 0, 1, 4]
m = 3

Initial window:

[2, 1, 3]
sum = 6
max = 6

Window 2

Remove 2, add 5:

[1, 3, 5]

sum = 6 - 2 + 5
= 9

max = 9

Window 3

Remove 1, add 0:

[3, 5, 0]

sum = 9 - 1 + 0
= 8

Window 4

[5, 0, 1]

sum = 8 - 3 + 1
= 6

Window 5

[0, 1, 4]

sum = 6 - 5 + 4
= 5

Circular Window 6

Now we need:

[1, 4, 2]

The 2 comes from the beginning of the array.

Because:

i % n

wraps the index around.

Sum:

1 + 4 + 2 = 7

Circular Window 7

[4, 2, 1]

sum = 4 + 2 + 1
= 7

Therefore:

maximum = 9

Why Is the Complexity O(n)?

We calculate the first window in O(m) time.

Then we slide the window around the array. Each step takes O(1) time because we only:

Remove one element.
Add one element.
Compare with the maximum.

Overall:

O(m) + O(n)

which is:

O(n)

The algorithm uses only a few variables:

n
k
windowSum
maxSum
i

Therefore:

Auxiliary Space = O(1)

Complexity

Metric	Complexity
Time	O(n)
Auxiliary Space	O(1)

This satisfies the expected complexity of the problem.

Important Note About int

With the stated constraints:

arr[i] <= 10^6
n <= 10^6

the total can theoretically reach:

10^6 × 10^6 = 10^12

which is larger than Java's int range.

So if the platform allows a long return type, the safer implementation is to use long for windowSum and maxSum. If the platform requires exactly:

public int maxFruits(ArrayList<Integer> arr, int m)

then keep the int signature as given by the problem.