Cyclic Array Maximization — Problem Statement & Solution Guide

ArraysMediumPrefix Sum and Cycle Detection

TimeO(n)

SpaceO(1)

Quick Answer & Algorithm Key Takeaway

Master coding challenges related to Arrays and solve the Cyclic Array Maximization problem optimally.

TopicArrays

PatternPrefix Sum and Cycle Detection

TimeO(n)

SpaceO(1)

Problem Description

Given a circular array resources of length n and an integer missions (1 ≤ missions ≤ n), you may choose any starting index and collect the values of missions consecutive elements while moving clockwise. When the end of the array is reached you continue from the beginning, i.e., the traversal is cyclic. Your task is to determine the greatest possible total that can be obtained.

DSA Pattern Breakdown

"Cyclic Array Maximization"

medium

WHY DOES IT MATTER?

Sliding‑window on a circular structure is a core pattern for any fixed‑size window query (max/min/average) where the data logically wraps, common in signal processing, networking buffers, and time‑series analytics.

OPTIMIZATION CHALLENGE

The insight is to view the circular array as a linear array of length 2n, which guarantees every wrap‑around window appears contiguously; then a single pass with a constant‑time update yields the optimum.

REAL-WORLD CONNECTION

Think of a rotating log buffer in a distributed system: you constantly read the last k entries as new logs arrive, discarding the oldest and adding the newest without re‑scanning the whole buffer.

In an interview, implement the sliding window using modulo arithmetic to avoid extra memory; start by computing the sum of the first k elements, then iterate i from 1 to n‑1 updating sum = sum - arr[(i‑1)%n] + arr[(i+k‑1)%n].

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(1)

Core Theory — Why This Approach?

The problem asks for the maximum sum of any contiguous sub‑array of length k (missions) on a circular array. A naïve solution would enumerate every possible start index, sum the next k elements (wrapping around when needed) and keep the best – this costs O(n·k) time, which is prohibitive when both n and k approach 10⁵. The optimal paradigm is the sliding‑window technique: maintain the sum of a window of size k as you move the start one step forward, updating the sum in O(1) by subtracting the element that leaves the window and adding the new entering element. To handle the wrap‑around, we conceptually concatenate the array to itself (or use modulo arithmetic) so that every possible window appears as a linear segment of length k in the doubled view. This yields an O(n) time, O(1) extra‑space solution, which scales to the largest constraints.

Why this works is rooted in the fact that the sum of a fixed‑size window is a linear function of its elements; the difference between consecutive windows is exactly the outgoing and incoming values. Hence recomputation is unnecessary. The sliding‑window pattern is a classic example of exploiting overlapping sub‑problems without full recomputation, turning a quadratic brute force into linear time.

Interview Questions on This Problem

Q1How would you find the maximum sum of k consecutive elements in a circular array in O(n) time?

Duplicate the array (or treat indices modulo n) and run a sliding window of size k across the first n positions, updating the window sum by subtracting the element leaving and adding the new element entering, tracking the maximum.

Q2What edge case must you handle when k equals the array length?

When k == n the window covers the entire array, so the answer is simply the total sum of all elements; the sliding‑window loop still works but you must avoid double‑counting by not sliding beyond the first position.

Q3Why is a prefix‑sum array not the best choice for this problem compared to a sliding window?

A prefix‑sum allows O(1) range queries but requires O(n) extra space and still needs O(n) time to evaluate all n possible windows; the sliding window achieves the same O(n) time with O(1) space and simpler implementation.

Examples

Example 1

Input

resources = [4,-1,2,5], missions = 3

Output

Explanation: Starting at index 2 (value 2) the three visited elements are 2, 5 (wrap to index 0), 4 → sum 2+5+4 = 11, which is larger than any other starting position.

Example 2

Input

resources = [-3,6,-2,7,-5], missions = 2

Output

Explanation: Evaluate every pair of consecutive elements (wrapping at the end): - start 0: -3+6 = 3 - start 1: 6+(-2) = 4 - start 2: -2+7 = 5 - start 3: 7+(-5) = 2 - start 4: -5+(-3) = -8 The maximum sum is 5, obtained from indices 2 and 3.

Example 3

Input

resources = [10,-2,-1,-3], missions = 4

Output

Explanation: Because missions equals the array length, the traversal must include every element exactly once. The total sum is 10 + (-2) + (-1) + (-3) = 4, which is the only possible result.

Constraints

1 <= resources.length <= 200000
1 <= missions <= resources.length
-10^9 <= resources[i] <= 10^9

Optimal Approach & Strategy

Use a sliding window of size k on a doubled view of the array, updating the sum in O(1) per step – O(n) time, O(1) space.

Brute Force Approach

For each start index compute the sum of the next k elements (wrapping around) and keep the maximum – O(n·k) time.

Code Solutions

Language:

JavaScript Solution

Time: O(n)

const fs = require('fs');
const data = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
let p = 0;
const n = data[p++];
const resources = data.slice(p, p+n); p+=n;
const missions = data[p] || 0;
function maxCyclicSum(resources, missions) {
    const n = resources.length;
    if (missions === 0) return 0;
    // create duplicated array virtually using modulo
    let sum = 0;
    for (let i = 0; i < missions; ++i) sum += resources[i];
    let best = sum;
    for (let start = 1; start < n; ++start) {
        sum += resources[(start + missions - 1) % n] - resources[start - 1];
        if (sum > best) best = sum;
    }
    return best;
}
console.log(maxCyclicSum(resources, missions).toString());

#include <bits/stdc++.h>
using namespace std;

long long maxCyclicSum(const vector<long long>& resources, int missions) {
    int n = resources.size();
    if(missions==0) return 0LL;
    // Duplicate the array to handle wrap‑around
    vector<long long> dup(resources);
    dup.insert(dup.end(), resources.begin(), resources.end());
    long long windowSum = 0;
    for(int i=0;i<missions;i++) windowSum += dup[i];
    long long best = windowSum;
    for(int i=1;i<n;i++) {
        windowSum += dup[i+missions-1] - dup[i-1];
        best = max(best, windowSum);
    }
    return best;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; if(!(cin>>n)) return 0;
    vector<long long> resources(n);
    for(int i=0;i<n;++i) cin>>resources[i];
    int missions; cin>>missions;
    cout<<maxCyclicSum(resources, missions);
    return 0;
}

import java.util.*;

public class Main {
    private static long maxCyclicSum(long[] resources, int missions) {
        int n = resources.length;
        if (missions == 0) return 0L;
        long window = 0L;
        for (int i = 0; i < missions; i++) window += resources[i];
        long best = window;
        for (int start = 1; start < n; start++) {
            window += resources[(start + missions - 1) % n] - resources[start - 1];
            if (window > best) best = window;
        }
        return best;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        if (!sc.hasNextInt()) return;
        int n = sc.nextInt();
        long[] resources = new long[n];
        for (int i = 0; i < n; i++) resources[i] = sc.nextLong();
        int missions = sc.nextInt();
        System.out.print(maxCyclicSum(resources, missions));
        sc.close();
    }
}

import sys

def max_cyclic_sum(resources, missions):
    n = len(resources)
    if missions == 0:
        return 0
    # initial window
    window = sum(resources[i] for i in range(missions))
    best = window
    for start in range(1, n):
        window += resources[(start + missions - 1) % n] - resources[start - 1]
        if window > best:
            best = window
    return best

def main():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    it = iter(data)
    n = int(next(it))
    resources = [int(next(it)) for _ in range(n)]
    missions = int(next(it))
    print(max_cyclic_sum(resources, missions))

if __name__ == "__main__":
    main()

const fs = require('fs');
const data = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
let p = 0;
const n = data[p++];
const resources = data.slice(p, p+n); p+=n;
const missions = data[p] || 0;
function maxCyclicSum(resources, missions) {
    const n = resources.length;
    if (missions === 0) return 0;
    // create duplicated array virtually using modulo
    let sum = 0;
    for (let i = 0; i < missions; ++i) sum += resources[i];
    let best = sum;
    for (let start = 1; start < n; ++start) {
        sum += resources[(start + missions - 1) % n] - resources[start - 1];
        if (sum > best) best = sum;
    }
    return best;
}
console.log(maxCyclicSum(resources, missions).toString());

Asked in Top Tech Interviews

Uber

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.