Max Gross Value of a Four-Way Array Split

Question

Given an array arr of n integers, a triplet of 1-based indices i1, i2, i3 with 1 ≤ i1 ≤ i2 ≤ i3 ≤ n + 1 cuts the array into four consecutive segments. Its gross value is

grossValue(i1, i2, i3) = sum[1, i1) - sum[i1, i2) + sum[i2, i3) - sum[i3, n + 1)

Here sum[l, r) (1 ≤ l ≤ r ≤ n + 1) uses half-open interval notation: the range includes index l and excludes index r. When l = r, arr[l, r) is empty and sum[l, r) is 0.

Find the maximum gross value of any valid triplet.

Constraints (as reported)

- n up to 3 * 10^3.

Notes from the reports

- This was one of two coding problems in a Citadel online assessment, reported three times between July and September 2025.
- In plain terms: cut the array into four pieces and maximise piece 1 - piece 2 + piece 3 - piece 4. Cuts may share a position, and a cut may sit before the first element or after the last, so pieces can be empty. The first report calls these a lot of edge cases.
- One report's copy of the prompt gives the first term as sum[i1, i2), repeating the second term. That candidate's own summary and another report's copy of the formula both make it sum[1, i1), which is what the statement above uses. If you get this prompt, check which the formula says.
- No worked example with an answer was posted.
- Not reported, so confirm or state your assumption: the range and sign of the values (the prompt says only "integers"), and whether the array can be empty.

AceOffer · Accepted Answer

Given an array arr of n integers, a triplet of 1-based indices i1, i2, i3 with 1 ≤ i1 ≤ i2 ≤ i3 ≤ n + 1 cuts the array into four consecutive segments. Its gross value is

grossValue(i1, i2, i3) = sum[1, i1) - sum[i1, i2) + sum[i2, i3) - sum[i3, n + 1)

Here sum[l, r) (1 ≤ l ≤ r ≤ n + 1) uses half-open interval notation: the range includes index l and excludes index r. When l = r, arr[l, r) is empty and sum[l, r) is 0.

Find the maximum gross value of any valid triplet.

Constraints (as reported)

- n up to 3 * 10^3.

Notes from the reports

- This was one of two coding problems in a Citadel online assessment, reported three times between July and September 2025.
- In plain terms: cut the array into four pieces and maximise piece 1 - piece 2 + piece 3 - piece 4. Cuts may share a position, and a cut may sit before the first element or after the last, so pieces can be empty. The first report calls these a lot of edge cases.
- One report's copy of the prompt gives the first term as sum[i1, i2), repeating the second term. That candidate's own summary and another report's copy of the formula both make it sum[1, i1), which is what the statement above uses. If you get this prompt, check which the formula says.
- No worked example with an answer was posted.
- Not reported, so confirm or state your assumption: the range and sign of the values (the prompt says only "integers"), and whether the array can be empty.

Common mistakes: Stopping at the O(n^3) enumeration of all cuts, which passed about 60% of the tests

What passers do: Fixing the cut between the second and third segments and precomputing the best prefix sum before it and the best suffix sum after it, for O(n) overall (a reply to the first report; another reply says they had just written a version that passed every test)

Why people fail: O(n^3) enumeration of all cuts: about 60% of the tests; Two test cases failing even with a brute force; the candidate suspected the test data

Edge cases probed: Cuts at the same position, leaving a segment empty; Cuts before the first element or after the last, leaving the first or last segment empty

Alternative approaches: Enumerate every triplet of cuts with prefix and suffix sums (O(n^3). The first poster reports it passed about 60% of the tests with n up to 3 * 10^3.); Fix the middle cut and scan both sides (O(n^2): for each middle cut, scan every first cut to its left and every third cut to its right. Posted in a second report's summary of the OA problems; no pass rate is given.); Fix the middle cut with precomputed prefix maximum and suffix minimum (O(n) after O(n) preprocessing. Given in a reply to the first report, and confirmed by the poster.)

Constraints (as reported)

Notes from the reports

Max Gross Value of a Four-Way Array Split

Problem Overview

Constraints (as reported)

Notes from the reports

Approach Trade-offs

What Reports Emphasize

Practice

Prepping for Citadel with friends?

More Citadel Questions

Every question in the Citadel catalog gets this depth

Approach	Notes
Enumerate every triplet of cuts with prefix and suffix sums	O(n^3). The first poster reports it passed about 60% of the tests with n up to 3 * 10^3.
Fix the middle cut and scan both sides	O(n^2): for each middle cut, scan every first cut to its left and every third cut to its right. Posted in a second report's summary of the OA problems; no pass rate is given.
Fix the middle cut with precomputed prefix maximum and suffix minimum	O(n) after O(n) preprocessing. Given in a reply to the first report, and confirmed by the poster.