Luogu P1121 Review: Maximum Sum of Two Circular Subarrays and Circular DP

Introduction

This article reviews my solution to P1121 Maximum Sum of Two Circular Subarrays on Luogu. The central algorithmic idea—combining case analysis with a complementary formulation—was correct in my first implementation. However, a boundary case caused by the nonempty constraint prevented that version from passing every test. I will examine exactly how that case arises, then show how a one-line fix takes the implementation from 80 points to the final 100-point solution.

Problem Analysis

The essential parts of the problem are:

1. Layout: The elements form a circle. a[1] and a[n] are adjacent, so a contiguous subarray can wrap from the end of the array back to the beginning.
2. Objective: Choose two nonoverlapping, nonempty contiguous subarrays with the largest possible total sum. The nonempty constraint is crucial when handling boundary cases.
3. Constraints: N can be as large as 2e5, so the algorithm must run in O(N) or O(N log N) time.

We need to maximize the sum of two subarrays on a circle. The challenge is to design a linear-time algorithm that handles both the circular structure and the requirement to choose two subarrays.

Algorithm Design and Implementation

V1.0: Initial Implementation (80 Points)

Design

Direct dynamic programming on a circle makes states difficult to define because there is no fixed starting or ending point. I therefore used the standard approach of breaking the circular problem into linear problems.

Every possible choice of two subarrays falls into one of two cases, depending on whether the selection crosses the connection between a[1] and a[n]:

1. Case 1: Neither chosen subarray crosses the a[1]–a[n] connection.
   • Reduction: This is equivalent to finding the maximum sum of two subarrays on the line a[1...n].
   • Solution: Enumerate a dividing point. There must be a dividing point between the two optimal subarrays S1 and S2 on the line.
     a. Use dynamic programming to precompute two auxiliary arrays:
     • max_L_to_R[i]: the maximum sum of a single subarray anywhere within the prefix a[1...i].
     • max_R_to_L[i]: the maximum sum of a single subarray anywhere within the suffix a[i...n].
       b. Iterate over every possible dividing point i, from 1 to n-1, and calculate max_L_to_R[i] + max_R_to_L[i+1].
       c. The largest of these sums is the answer for Case 1.

Figure legend: The red outline is the circular array, with the cut between a[n] and a[1]. Purple arcs mark the selected subarrays. The handwritten label means “does not cross the cut.”

2. Case 2: The chosen subarrays cross the a[1]–a[n] connection.
   • Reduction: In this case, one subarray lies at the end of the array and the other at the beginning. To simplify the calculation, consider the complement.
   • Reasoning: (选中元素的和) = (数组总和) - (未选中元素的和). In English: the sum of selected elements equals the total array sum minus the sum of unselected elements.
   • Key observation: If the selected portion wraps around, the unselected portion must not wrap around.
   • Further reduction: Maximizing the sum of selected elements is equivalent to minimizing the sum of unselected elements.
   • Solution:
     a. Reduce the problem to finding the minimum sum of two subarrays on the line a[1...n].
     b. Use the symmetric version of the method from Case 1: compute min_L_to_R and min_R_to_L, then find the minimum sum of two subarrays on the line.
     c. Subtract this value from 数组总和, the total array sum, to obtain the answer for Case 2.

Figure legend: The purple selection crosses the cut between a[n] and a[1]. The handwritten label means “crosses the cut.” The unselected portions remain ordinary subarrays on the line.

The final answer is max(情况一的解, 情况二的解): the larger of the answers for Case 1 and Case 2. The algorithm runs in O(N) time.

Implementation

80-point submission record

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll const maxn = 2e5 + 5, minn = -1e9;

int n;
ll total_a, a[maxn], max_L_to_R[maxn], dp_max_L_to_R[maxn], max_R_to_L[maxn], dp_max_R_to_L[maxn], min_L_to_R[maxn], dp_min_L_to_R[maxn], min_R_to_L[maxn], dp_min_R_to_L[maxn];

void find_L_to_R() {
    ll max_val = minn, min_val = maxn;
    for (int i = 1; i <= n; ++i) {
        dp_max_L_to_R[i] = max(dp_max_L_to_R[i - 1] + a[i], a[i]);
        max_val = max(max_val, dp_max_L_to_R[i]);
        max_L_to_R[i] = max_val;
        dp_min_L_to_R[i] = min(dp_min_L_to_R[i - 1] + a[i], a[i]);
        min_val = min(min_val, dp_min_L_to_R[i]);
        min_L_to_R[i] = min_val;
    }
}

void find_R_to_L() {
    ll max_val = minn, min_val = maxn;
    for (int i = n; i >= 1; --i) {
        dp_max_R_to_L[i] = max(dp_max_R_to_L[i + 1] + a[i], a[i]);
        max_val = max(max_val, dp_max_R_to_L[i]);
        max_R_to_L[i] = max_val;
        dp_min_R_to_L[i] = min(dp_min_R_to_L[i + 1] + a[i], a[i]);
        min_val = min(min_val, dp_min_R_to_L[i]);
        min_R_to_L[i] = min_val;
    }
}

ll case_1() {
    ll max_val = minn;
    for (int i = 1; i < n; ++i) {
        max_val = max(max_val, max_L_to_R[i] + max_R_to_L[i + 1]);
    }
    return max_val;
}

ll case_2() {
    ll min_val = maxn;
    for (int i = 1; i < n; ++i) {
        min_val = min(min_val, min_L_to_R[i] + min_R_to_L[i + 1]);
    }
    return total_a - min_val;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        total_a += a[i];
    }
    find_L_to_R();
    find_R_to_L();
    cout << max(case_1(), case_2());
    return 0;
}

What Went Wrong

• Root cause:
  The theoretical model is correct, but the implementation misses a special case introduced by the nonempty constraint. It fails on tests where the input array contains only negative numbers.

• Why it fails:

  1. When every element is negative, minimizing the sum means choosing as many elements as possible. The computed minimum sum of two subarrays on the line therefore equals the total array sum.
  2. The calculation total_a - min_val in case_2() then becomes total_a - total_a, producing 0.
  3. Under the nonempty constraint, the sum of any two nonempty subarrays in an all-negative array must be negative. case_1() correctly computes the optimal negative result.
  4. Finally, main compares max(一个正确的负数, 0)—the larger of the correct negative value and zero—and incorrectly chooses 0.
  5. This result of 0 corresponds to leaving every element unselected, or selecting the empty set, which violates the problem’s nonempty constraint.

V2.0: Corrected Implementation (AC)

Design

The problem is now clear: when the minimum sum of two subarrays on the line == total array sum, case_2() produces an invalid answer of 0.

The fix must recognize this situation and ensure that the invalid result cannot become the final answer.

• Solution: Change the return value of case_2(). When total_a == min_val, return the smallest possible sentinel value, LLONG_MIN, rather than 0.
• Effect: Every valid solution, including a negative one, must be greater than LLONG_MIN. In the final max comparison, the valid answer from case_1() therefore automatically replaces the LLONG_MIN returned by case_2(), ensuring a correct result.

Implementation

Accepted submission record

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll const maxn = 2e5 + 5;

int n;
ll total_a, a[maxn], max_L_to_R[maxn], dp_max_L_to_R[maxn], max_R_to_L[maxn], dp_max_R_to_L[maxn], min_L_to_R[maxn], dp_min_L_to_R[maxn], min_R_to_L[maxn], dp_min_R_to_L[maxn];

void find_L_to_R() {
    ll max_val = LLONG_MIN, min_val = LLONG_MAX;
    for (int i = 1; i <= n; ++i) {
        dp_max_L_to_R[i] = max(dp_max_L_to_R[i - 1] + a[i], a[i]);
        max_val = max(max_val, dp_max_L_to_R[i]);
        max_L_to_R[i] = max_val;
        dp_min_L_to_R[i] = min(dp_min_L_to_R[i - 1] + a[i], a[i]);
        min_val = min(min_val, dp_min_L_to_R[i]);
        min_L_to_R[i] = min_val;
    }
}

void find_R_to_L() {
    ll max_val = LLONG_MIN, min_val = LLONG_MAX;
    for (int i = n; i >= 1; --i) {
        dp_max_R_to_L[i] = max(dp_max_R_to_L[i + 1] + a[i], a[i]);
        max_val = max(max_val, dp_max_R_to_L[i]);
        max_R_to_L[i] = max_val;
        dp_min_R_to_L[i] = min(dp_min_R_to_L[i + 1] + a[i], a[i]);
        min_val = min(min_val, dp_min_R_to_L[i]);
        min_R_to_L[i] = min_val;
    }
}

ll case_1() {
    ll max_val = LLONG_MIN;
    for (int i = 1; i < n; ++i) {
        max_val = max(max_val, max_L_to_R[i] + max_R_to_L[i + 1]);
    }
    return max_val;
}

ll case_2() {
    ll min_val = LLONG_MAX;
    for (int i = 1; i < n; ++i) {
        min_val = min(min_val, min_L_to_R[i] + min_R_to_L[i + 1]);
    }
    return total_a == min_val ? LLONG_MIN : total_a - min_val;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        total_a += a[i];
    }
    find_L_to_R();
    find_R_to_L();
    cout << max(case_1(), case_2());
    return 0;
}

• Implementation detail
  The central change is the return statement in case_2():
  return total_a == min_val ? LLONG_MIN : total_a - min_val;
  This line uses the ternary operator to keep both the special-case check and its handling inside the function, resolving the problem.

• Improved robustness
  The AC code replaces every hard-coded large or small initialization value, such as 1e9, with LLONG_MAX and LLONG_MIN from the standard library’s <climits>. This removes the dependency on assumptions about the input range and makes the code more general and robust.

P.S. The complete handwritten notes:

Figure legend: The top shows the sample array and its circular layout. “Case 1” means the selection does not cross the cut; “Case 2” means it does. Purple arcs indicate the selected portions in each sketch.

Takeaways

1. Handling circular problems: Combining case analysis with a complementary formulation is an effective way to turn this kind of circular-array problem into calculations on a line.
2. Boundary cases matter: Special datasets such as all-positive and all-negative arrays need explicit analysis. Constraints such as nonempty can determine correctness precisely at these boundaries.
3. A technique for invalid answers: If one branch of an algorithm can produce a logically invalid result, return a value that the final aggregation operation, such as max or min, will always discard—for example, LLONG_MIN or LLONG_MAX. This avoids complicated checks outside the branch.