Problem Statement

You are given a circular number wheel with N slots, each containing a non-negative integer. You can rotate the wheel clockwise any number of times (i.e., shift all elements right, wrapping the last to the front).

Your task is to determine the maximum possible sum of any K consecutive elements on the wheel after any number of rotations.

Input: The first line contains two integers N and K (1 ≤ K ≤ N ≤ 10⁴) The second line contains N integers A₁, A₂, ..., Aₙ (0 ≤ Aᵢ ≤ 1000)

Output A single integer: the maximum possible sum of any K consecutive numbers on the wheel.

Example

5 2 4 2 1 7 5

result = 12

Here is my solution in java in O(n2)

import java.util.*;

public class MaxRotatedSegment {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(), K = sc.nextInt();
        int[] A = new int[N];
        for (int i = 0; i < N; i++) A[i] = sc.nextInt();

        int result = getMaxRotatedSegmentSum(A, K);
        System.out.println(result);
    }

    public static int getMaxRotatedSegmentSum(int[] A, int K) {
        int N = A.length;
        int maxSum = 0;

        for (int r = 0; r < N; r++) {
            int[] rotated = new int[N];
            for (int i = 0; i < N; i++) {
                rotated[i] = A[(i + r) % N];
            }
            for (int i = 0; i <= N - K; i++) {
                int sum = 0;
                for (int j = 0; j < K; j++) {
                    sum += rotated[i + j];
                }
                maxSum = Math.max(maxSum, sum);
            }
        }
        return maxSum;
    }
}

The current solution has a time complexity of O(n2) in the worst case, which may time out for n = 10⁴.

Can anyone please suggest a more optimal solution in O(nlogn) or O(n)