Max Over Feasible Candidates

The $k$-th sorted subarray in the optimal partition occupies some contiguous range $a[i..j]$. In any partition where $a[i..j]$ is a subarray, every other subarray lies entirely in $a[0..i-1]$ (left subarrays) or $a[j+1..n-1]$ (right subarrays).

Let there be $m$ left subarrays and $r$ right subarrays. Then $m + 1 + r \ge k$ and, because every subarray has length $\ge l$:

• $m \cdot l \le i$ (so $m \le \lfloor i/l\rfloor$; $i = 0$ or $i \ge l$);
• $r \cdot l \le n-1-j$ (so $r \le \lfloor (n-1-j)/l\rfloor$; $j = n-1$ or $j \le n-1-l$).

Don’t ask “can $a[i..j]$ be the $k$-th sorted subarray?” — that involves sort order and is hard.

Do ask “can $a[i..j]$ appear as some subarray (rank irrelevant) in some valid partition?” This is a pure counting question.

Call $(i, j)$ feasible iff:

1. $j - i + 1 \ge l$;
2. $i = 0$ or $i \ge l$;
3. $n-1-j = 0$ or $n-1-j \ge l$;
4. $\left\lfloor\dfrac{i}{l}\right\rfloor + \left\lfloor\dfrac{n-1-j}{l}\right\rfloor \ge k-1$.

Claim. $\displaystyle \text{answer} \;=\; \max\bigl\{\,\mathrm{sum}(a[i..j]) \,:\, (i,j)\text{ feasible}\,\bigr\}.$

Prove both directions.

Upper bound. The optimal $k$-th sorted subarray $a[i^*..j^*]$ is a subarray of the optimal partition, so $(i^*, j^*)$ is feasible, so $\mathrm{sum}(a[i^*..j^*]) \le$ max feasible sum.

Lower bound. For the arg-max feasible $(i^*, j^*)$, build a partition with exactly $k$ subarrays:

• $m = \min(\lfloor i^*/l\rfloor, k-1)$ left subarrays covering $a[0..i^*-1]$, each of length $\ge l$;
• $a[i^*..j^*]$ in the middle;
• $r = k-1-m$ right subarrays covering $a[j^*+1..n-1]$, each of length $\ge l$.

Feasibility (condition 4) guarantees such $m, r$ exist. Total $=$ exactly $k$ subarrays, so the $k$-th sorted $=$ max $\ge$ candidate sum.

(The $k=2$ corner case with $i^* > 0$ and $j^* < n-1$ is handled as in problem F: at a lex/value max, the candidate can always be pushed to have $i^*=0$ or $j^*=n-1$, because since $a_i \ge 0$ extending a subarray only increases its sum.)

Precompute prefix sums $S[0..n]$ so that $\mathrm{sum}(a[i..j]) = S[j+1] - S[i]$ is computed in $O(1)$.

best = -1
for i in 0..n-1:
    if i != 0 and i < l: continue
    pre_cnt = i // l
    for j in i+l-1..n-1:
        suf = n-1-j
        if suf != 0 and suf < l: continue
        suf_cnt = suf // l
        if pre_cnt + suf_cnt < k - 1: continue
        s = S[j+1] - S[i]
        if s > best: best = s

print best

• Outer pairs $(i,j)$: $O(n^2)$.
• Per-pair work: $O(1)$ (thanks to prefix sums).
• Total: $O(n^2)$.

(On strings we needed $O(n^3)$ because each lex comparison was $O(n)$; here the “comparison” is just comparing two integers in $O(1)$.)

For non-negative $a_i$, longer is always at least as good (extending a subarray cannot decrease its sum). So for fixed $i$, the best feasible $j$ is the maximum feasible $j$, namely

That collapses the algorithm to $O(n)$ candidates, giving $O(n)$ total after prefix sums — identical to problem F’s O(n²) refinement, just with “sum” instead of “lex”.

If $a$ contains negative values, the “longer is better” step fails, but the $O(n^2)$ brute force from Hint 4 still works unchanged.

Every subarray of the partition is $a[i..j]$ for some indices. If $a[i..j]$ is the $k$-th sorted, then besides it we have $m$ left subarrays in $a[0..i-1]$ and $r$ right subarrays in $a[j+1..n-1]$, each of length $\ge l$, with $m + r \ge k-1$.

Instead of “$a[i..j]$ is the $k$-th sorted”, ask “$a[i..j]$ is some subarray”. The feasibility condition becomes a pure counting one:

1. $j - i + 1 \ge l$.
2. $i \in \{0\}\cup[l,n-1]$.
3. $n-1-j \in \{0\}\cup[l,n-1]$.
4. $\lfloor i/l\rfloor + \lfloor (n-1-j)/l\rfloor \ge k-1$.

$\text{answer} = \max_{(i,j)\text{ feasible}} \mathrm{sum}(a[i..j])$.

Upper bound. The optimal $k$-th sorted subarray $a[i^*..j^*]$ is itself a subarray of the optimal partition, hence $(i^*, j^*)$ is feasible.

Lower bound. For max-feasible $(i^*, j^*)$, construct a partition with exactly $k$ subarrays: $m$ left covering $[0, i^*-1]$, candidate, $r$ right covering $[j^*+1, n-1]$, with $m + r = k-1$ (possible by condition 4). Among exactly $k$ subarrays the $k$-th sorted is the max, which is $\ge$ the candidate’s sum.

long long best = -1;
vector<long long> S(n + 1, 0);
for (int t = 0; t < n; t++) S[t+1] = S[t] + a[t];

for (int i = 0; i < n; i++) {
    if (i != 0 && i < l) continue;
    long long pre_cnt = i / l;
    for (int j = i + l - 1; j < n; j++) {
        int suf = n - 1 - j;
        if (suf != 0 && suf < l) continue;
        long long suf_cnt = suf / l;
        if (pre_cnt + suf_cnt < k - 1) continue;
        best = max(best, S[j+1] - S[i]);
    }
}

$n=9, l=2, k=3, a=[3,1,4,1,5,9,2,6,5]$, $S = [0, 3, 4, 8, 9, 14, 23, 25, 31, 36]$.

We need $\lfloor i/2\rfloor + \lfloor (8-j)/2\rfloor \ge 2$, with appropriate prefix/suffix length checks. The feasible $(i, j)$ pair maximizing $S[j+1] - S[i]$ turns out to be $(4, 8)$:

• $\lfloor 4/2\rfloor + \lfloor 0/2\rfloor = 2 + 0 = 2 \ge 2$. ✓
• $\mathrm{sum}(a[4..8]) = 5+9+2+6+5 = 27$.

Matches the expected answer $27$. Partition: $[3,1]\,|\,[4,1]\,|\,[5,9,2,6,5]$ with sorted sums $4, 5, 27$.

See sol/code.