A good way into this one is to ask: what do we need to remember so we never redo work blindly? For 918. Maximum Sum Circular Subarray, the solution in this repository is mainly a dynamic programming solution.
Guide
What?
The code is easier to read if we treat it as a controlled search through possible states. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: dynamic programming, sliding window, prefix sums.
The notes already sitting in the source point us in the right direction:
- TLE
- 94 / 109 test cases passed.
Guide
When?
Reach for this shape when a direct simulation would work logically but waste time revisiting the same information. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are maxSubarraySumCircular, rightsums, maxrights, P, kadane.
Guide
Why?
The code is doing bookkeeping so your brain does not have to keep the entire search space open at once.
- The two-dimensional vector is the memory of the solution: grid state, DP state, or adjacency shape.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Read the setup variables first.
- Follow the main loop or recursive helper next.
- Watch where invalid states get skipped.
- Check which value survives to the return statement.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//TLE
02//94 / 109 test cases passed.
03class Solution {
04public:
05 int maxSubarraySumCircular(vector<int>& A) {
06 int n = A.size();
07
08 vector<vector<int>> dp(n, vector(n, INT_MIN));
09 int ans = INT_MIN;
10
11 //i: start
12 for(int i = n-1; i >= 0; i--){
13 //j: end
14 //the upper bound(exclusive) changes from n to i+n -> circular
15 for(int j = i; j < i+n; j++){
16 //length 1 subarray
17 if(i == j){
18 dp[i][j%n] = A[i];
19 }else{
20 dp[i][j%n] = max({dp[i][j%n],
21 (dp[(i+1)%n][j%n] == INT_MIN) ? INT_MIN : A[i]+dp[(i+1)%n][j%n],
22 (dp[i][(j-1+n)%n] == INT_MIN) ? INT_MIN : dp[i][(j-1+n)%n]+A[j%n]
23 });
24 }
25
26 // if(dp[i][j%n] > ans){
27 // cout << "[" << i << ", " << j << "]: " << dp[i][j%n] << endl;
28 // }
29 ans = max(ans, dp[i][j%n]);
30 }
31 }
32
33 return ans;
34 }
35};
36
37//Kadane's Algorithm
38//https://medium.com/@rsinghal757/kadanes-algorithm-dynamic-programming-how-and-why-does-it-work-3fd8849ed73d
39//O(n)
40/*
41class Solution {
42public:
43 int maxSubarraySumCircular(vector<int>& A) {
44 int n = A.size();
45 int localMax = INT_MIN; // max sum of subarray which ends at i
46 int globalMax = INT_MIN;
47
48 for(int i = 0; i < n; i++){
49 //enlong the old subarray or create a new one starting from i
50 localMax = max(A[i], (localMax == INT_MIN) ? INT_MIN : A[i] + localMax);
51 globalMax = max(globalMax, localMax);
52 }
53
54 return globalMax;
55 }
56};
57*/
58
59//Approach 1: Next Array
60//Runtime: 172 ms, faster than 8.63% of C++ online submissions for Maximum Sum Circular Subarray.
61//Memory Usage: 43.2 MB, less than 8.33% of C++ online submissions for Maximum Sum Circular Subarray.
62//time: O(n), space: O(n)
63class Solution {
64public:
65 int maxSubarraySumCircular(vector<int>& A) {
66 int n = A.size();
67
68 //kadane's algorithm
69 int localMax = INT_MIN, globalMax = INT_MIN;
70
71 for(int i = 0; i < n; i++){
72 localMax = max(localMax, 0) + A[i];
73 globalMax = max(globalMax, localMax);
74 }
75
76 //now consider 2-interval subarrays
77 vector<int> rightsums(n);
78
79 rightsums[n-1] = A[n-1];
80 for(int i = n-2; i >= 0; i--){
81 rightsums[i] = rightsums[i+1] + A[i];
82 }
83
84 //max rightsum starts at >= i
85 vector<int> maxrights(n, 0);
86
87 for(int i = n-1; i >= 0; i--){
88 maxrights[i] = max((i+1 >= n ? INT_MIN : maxrights[i+1]), rightsums[i]);
89 }
90
91 /*
92 leftsum: [0...i]
93 maxrights[i+2]: max of rightsum starts from i+2
94 start from i+2 to ensure this is a 2-interval subarray
95 */
96 int leftsum = 0;
97 for(int i = 0; i+2 < n; i++){
98 leftsum += A[i];
99 globalMax = max(globalMax, leftsum + maxrights[i+2]);
100 }
101
102 return globalMax;
103 }
104};
105
106//Approach 2: Prefix Sums + Monoqueue(deque)
107//Runtime: 204 ms, faster than 6.83% of C++ online submissions for Maximum Sum Circular Subarray.
108//Memory Usage: 44.9 MB, less than 8.33% of C++ online submissions for Maximum Sum Circular Subarray.
109//time: O(n), space: O(n)
110class Solution {
111public:
112 int maxSubarraySumCircular(vector<int>& A) {
113 int n = A.size();
114
115 /*
116 image an array B = A + A,
117 P[i] is the prefix sum of B: ends at i-1,
118 so P[0] is 0, P[1] is A[0], ...
119 */
120 vector<int> P(2*n+1, 0);
121 for(int i = 0; i < 2*n; i++){
122 P[i+1] = P[i] + A[i%n];
123 }
124
125 int ans = A[0];
126 deque<int> dq;
127 dq.push_back(0);
128
129 //ends at j, exclusive
130 for(int j = 1; j <= 2*n; j++){
131 //subarray starts at dq.front()
132 if(j-dq.front() > n){
133 //if subarray's length > N, ignore this candidate
134 dq.pop_front();
135 }
136
137 ans = max(ans, P[j] - P[dq.front()]);
138
139 while(!dq.empty() && P[j] <= P[dq.back()]){
140 /*
141 j is the better starting point then dq.back(),
142 because P[j] is smaller, so P[later_j] - P[starting point]
143 can be larger
144 */
145 dq.pop_back();
146 }
147
148 //push candidate starting index
149 dq.push_back(j);
150 }
151
152 return ans;
153 }
154};
155
156//Approach 3: Kadane's (Sign Variant)
157//Runtime: 160 ms, faster than 18.47% of C++ online submissions for Maximum Sum Circular Subarray.
158//Memory Usage: 40.2 MB, less than 8.33% of C++ online submissions for Maximum Sum Circular Subarray.
159//time: O(n), space: O(1)
160class Solution {
161public:
162 int kadane(vector<int>& A, int start, int end, int sign){
163 int cur = INT_MIN, ans = INT_MIN;
164
165 for(int i = start; i <= end; i++){
166 cur = sign * A[i] + max(cur, 0);
167 ans = max(ans, cur);
168 }
169
170 return ans;
171 };
172
173 int maxSubarraySumCircular(vector<int>& A) {
174 int sum = accumulate(A.begin(), A.end(), 0);
175 int n = A.size();
176
177 //1-interval
178 int ans1 = kadane(A, 0, n-1, 1);
179 //2-intervals
180 /*
181 cannot set start as 0 and end as n-1,
182 if so, we may choose the empty array
183 */
184 int tmp;
185 /*
186 The two intervals are [0...i] and [j...n-1]
187 we need to make sure that the final subarray is not empty,
188 that is, to make sure kadane algorithm don't give a subarray which is equal to A
189 */
190 int ans2 = ((tmp = kadane(A, 1, n-1, -1)) == INT_MIN) ? INT_MIN : (tmp + sum);
191 int ans3 = ((tmp = kadane(A, 0, n-2, -1)) == INT_MIN) ? INT_MIN : (tmp + sum);
192
193 return max({ans1, ans2, ans3});
194 }
195};
196
197//Approach 4: Kadane's (Min Variant)
198//Runtime: 160 ms, faster than 18.47% of C++ online submissions for Maximum Sum Circular Subarray.
199//Memory Usage: 40.2 MB, less than 8.33% of C++ online submissions for Maximum Sum Circular Subarray.
200//time: O(n), space: O(1)
201class Solution {
202public:
203 int kadaneMin(vector<int>& A, int start, int end){
204 int cur = INT_MAX, ans = INT_MAX;
205
206 for(int i = start; i <= end; i++){
207 cur = A[i] + min(cur, 0);
208 ans = min(ans, cur);
209 }
210
211 return ans;
212 };
213
214 int kadane(vector<int>& A, int start, int end){
215 int cur = INT_MIN, ans = INT_MIN;
216
217 for(int i = start; i <= end; i++){
218 cur = A[i] + max(cur, 0);
219 ans = max(ans, cur);
220 }
221
222 return ans;
223 };
224
225 int maxSubarraySumCircular(vector<int>& A) {
226 int sum = accumulate(A.begin(), A.end(), 0);
227 int n = A.size();
228
229 //1-interval
230 int ans1 = kadane(A, 0, n-1);
231 //2-intervals
232 /*
233 cannot set start as 0 and end as n-1,
234 if so, we may choose the empty array
235 */
236 int tmp;
237 int ans2 = ((tmp = kadaneMin(A, 1, n-1)) == INT_MAX) ? INT_MIN : (sum - tmp);
238 int ans3 = ((tmp = kadaneMin(A, 0, n-2)) == INT_MAX) ? INT_MIN : (sum - tmp);
239
240 return max({ans1, ans2, ans3});
241 }
242};Cost
Complexity
Time
O(n) to O(n log n), depending on the dominant loop or data structure operation
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.