Maximum Slice Problem for app.codility.com/programmers Explained in C
Category of Article : Technology | Computers and Software | Algorithm
By: Chrysanthus Date Published: 30 Jul 2025
Maximum Slice Problem is also known as Maximum Sub-array Problem. Consider a maximum slice problem as follows: You are given a sequence of n integers a0 , a1 , . . . , an−1 , and the task is to find the slice with the largest sum. More precisely, we are looking for two indices p, q such that the total ap + ap+1 + . . . + aq is maximal. We assume that the slice can be empty and its sum equals 0.
| Variable | a0 | a1 | a2 | a3 | a4 | a5 | a6 | a7 |
|---|---|---|---|---|---|---|---|---|
| Value | 5 | -7 | 3 | 5 | -2 | 4 | -1 | -5 |
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
In the table, the slice with the largest sum is highlighted in gray. The sum of this slice equals 10 and there is no slice with a larger sum. Notice that the slice we are looking for, may contain negative integers, as shown above.
Note
p can be equal to q. The slice includes the values for the indexes, p and q.Solution with O(n3) Time Complexity
The simplest approach is to analyze all the slices and choose the one with the largest sum. Assume that there are 8 elements in the list. All the possible slices from a0 to a7, beginning with a0 are:a0
a0 + a1
a0 + a1 + a2
a0 + a1 + a2 + a3
a0 + a1 + a2 + a3 + a4
a0 + a1 + a2 + a3 + a4 + a5
a0 + a1 + a2 + a3 + a4 + a5 + a6
a0 + a1 + a2 + a3 + a4 + a5 + a6 + a7
There are 28 operations (additions) in this table. Now,
n.long2n = 8 x log2(8) = 8 x 3 = 24
8 x 8 = 82 = 64
28 operations is above 24 operations. Since in the topic of time complexity, it is the highest possible number of operations that is taken, the time complexity for the above table is given as, O(n2). When n = 8, O(n2) means O(82), which is equal to O(64), referring to a square table.
All the possible slices from a1 to a7, beginning with a1 are:
a1
a1 + a2
a1 + a2 + a3
a1 + a2 + a3 + a4
a1 + a2 + a3 + a4 + a5
a1 + a2 + a3 + a4 + a5 + a6
a1 + a2 + a3 + a4 + a5 + a6 + a7
This table can still be considered to have a time complexity of O(n2), though it consists of 21 actual operations. As n = 8, O(82) = O(64).
The actual number of operations so far is 28 + 21 = 49.
The possible addition of a0, has already been taken care of, in the previous table.
All the possible slices from a2 to a7, beginning with a2 are:
a2
a2 + a3
a2 + a3 + a4
a2 + a3 + a4 + a5
a2 + a3 + a4 + a5 + a6
a2 + a3 + a4 + a5 + a6 + a7
This table can still be considered to have a time complexity of O(n2), though it consists of 15 actual operations. As n = 8, O(82) = O(64).
The actual number of operations so far is 28 + 21 + 15 = 64.
All the possible additions from a0 to a1 , have already been taken care of, in the previous tables.
All the possible slices from a3 to a7, beginning with a3 are:
a3
a3 + a4
a3 + a4 + a5
a3 + a4 + a5 + a6
a3 + a4 + a5 + a6 + a7
This table can still be considered to have a time complexity of O(n2), though it consists of 10 actual operations. As n = 8, O(82) = O(64).
The actual number of operations so far is 28 + 21 + 15 + 10 = 74.
All the possible additions from a0 to a2 , have already been taken care of, in the previous tables.
All the possible slices from a4 to a7, beginning with a4 are:
a4
a4 + a5
a4 + a5 + a6
a4 + a5 + a6 + a7
This table can still be considered to have a time complexity of O(n2), though it consists of 6 actual operations. As n = 8, O(82) = O(64).
The actual number of operations so far is 28 + 21 + 15 + 10 + 6 = 80.
All the possible additions from a0 to a3 , have already been taken care of, in the previous tables.
All the possible slices from a5 to a7, beginning with a5 are:
a5
a5 + a6
a5 + a6 + a7
This table can still be considered to have a time complexity of O(n2), though it consists of 3 actual operations. As n = 8, O(82) = O(64).
The actual number of operations so far is 28 + 21 + 15 + 10 + 6 + 3 = 83.
All the possible additions from a0 to a4 , have already been taken care of, in the previous tables.
All the possible slices from a6 to a7, beginning with a6 are:
a6
a6 + a7
This table can still be considered to have a time complexity of O(n2), though it consists of 1 actual operation. As n = 8, O(82) = O(64).
The actual number of operations so far is 28 + 21 + 15 + 10 + 6 + 3 + 1 = 84.
All the possible additions from a0 to a6 , have already been taken care of, in the previous tables.
All the possible slices from a7 to a7, beginning with a7 are:
a7
No operation here (in theory).
The actual number of operations so far remains at 28 + 21 + 15 + 10 + 6 + 3 + 1 = 84.
Ideally, the total number of operations above is: 82 + 82 + 82 + 82 + 82 + 82 + 82 + 82 = 82 x 8 = 83 = 512.
Now, 8 x 8 = 82 = 64.
8 x 8 x 8 = 83 = 512
The actual number of operations for the algorithm, is 84, which lies between 64 and 512. That is, it lies between 82 and 83. Since the maximum possible number of operations is what is considered for time complexity, the time complexity for this algorithm is given by O(512) = O(83). In general terms, the time complexity for this algorithm is written as O(n3). The time to look for the maximum slice sum has been ignored.
Code for O(n3)
For the solution function, and taking the above 8 elements as an example, first take into consideration, all the 8 groups (n triangles), i.e. i from 0 to < n. That makes one for-loop, the outermost for-loop. Each group consists of a number of the slice sums, but do not add yet. Next, take into consideration the fact that a row addition starts from i + 1 for each group, as the groups are displayed above, going downwards, i.e. from j=i to < n. That makes a nested for-loop. Note that each row addition for any of the groups does not end at n-1; it ends at the row ordinal number minus 1. That makes the innermost for-loop, i.e. from k=i to <= j. The innermost for-loop does the actual addition, for each effective row. The sum is re-setted before the innermost for-loop is entered. Just after the innermost for-loop completes each time, the sum of an effective row is compared with the presumed largest slice sum; and the bigger is chosen. The fmax() function, for maximum, is in the math.h library, which has to be imported.So there are three for-loops, with the innermost nested to another, which is nested to the outer for-loop. The program is:
#include <stdio.h>
#include <math.h>
int slow_max_slice(int A[], int n) {
int largest_sum = -15; //assumed sum of all -ve numbers, assuming all +ve numbers were 0
for (int i=0; i<n; i++) {
for (int j=i; j<n; j++) {
int sum = 0;
for (int k=i; k<=j; k++) {
sum = sum + A[k];
}
largest_sum = fmax(largest_sum, sum);
}
}
return largest_sum;
}
int main(int argc, char **argv)
{
int A[] = {5, -7, 3, 5, -2, 4, -1, -5};
int n = sizeof(A)/sizeof(A[0]);
int ret = slow_max_slice(A, n);
printf("%i\n", ret);
return 0;
}
The O(n3) time complexity refers to the three for-loops, for this situation.Solution with O(n2 + n) Time Complexity
This approach uses prefix-sums. Remember that prefix-sums can reduce time complexity from O(n2) to O(n). The above solution involves a lot of addition of consecutive elements. So, it should occur to the reader, that prefix-sums may be used, to reduce the total number of operations, effectively reducing the time complexity for the whole code of interest, from O(n3) to O(n2).Each of the different possible rows in the above tables, is the sum of one of the slices for the whole list. If prefix-sums are obtained in O(n) time first, then each of the slice sum will be obtained in constant time, O(1), and the total number of operations with the high limits, will be n x n x 1= n2, without including the prefix summing in the time complexity. If the prefix-summing is to be included in the time complexity, then the number of operations with the high limits will be n x n x 1 + n = n2 + n. Remember that with prefix sums, the sum of a slice is the difference between the prefix sum at the beginning of the range (slice) and the prefix sum just after the range (slice). This difference is done in constant time.
So, the innermost for-loop above is replaced with the difference of prefix-sums (slice sum) of constant time, O(1). The O(n2 + n) solution function is:
#include <stdio.h>
#include <math.h>
int nSqrPlusN(int A[], int n) {
int largest_sum = -15; //assumed sum of all -ve numbers, assuming all +ve numbers were 0
int Pr[n+1];
for (int i=0; i<n+1; i++) //initializing all prefix elements to 0
Pr[i] = 0;
for (int k=1; k<n+1; k++)
Pr[k] = Pr[k - 1] + A[k - 1]; //prefix summing, O(n)
for (int i=0; i<n; i++) { // O(n square)
for (int j=i; j<n; j++) {
int sum = Pr[j+1] - Pr[i]; //prefix sums go up to n+1
largest_sum = fmax(largest_sum, sum);
}
}
return largest_sum;
}
int main(int argc, char **argv)
{
int A[] = {5, -7, 3, 5, -2, 4, -1, -5};
int n = sizeof(A)/sizeof(A[0]); //size of array divided by size of one (first) element
int ret = nSqrPlusN(A, n);
printf("%i\n", ret);
return 0;
}
int main(int argc, char **argv)
{
vector<int> A = {5, -7, 3, 5, -2, 4, -1, -5};
int ret = nSqrPlusN(A);
cout << ret << endl;
return 0;
}
Solution with O(n2) Time Complexity
With the above code, for each group, the slice sum is obtained by subtracting prefix sums. Why not include the prefix summing in the for-loops? If that is done, the extra O(n) number of operations for prefix sums will be eliminated, resulting in O(n2) main operations.Well, in the following code, prefix summing is done as follows: As the inner for-loop for the two for-loops above, is iterating each group (triangle) of rows, the row sums for the different row slices are obtained, by adding the next number to the previous sum. That is the slice sum already. The O(n2) solution function is:
int quadratic_max_slice(int A[], int n) {
int largest_sum = -15; //sum of all -ve numbers, assuming all +ve numbers were 0
for (int i=0; i<n; i++) {
int sum = 0;
for (int j=i; j<n; j++) {
sum = sum + A[j];
largest_sum = max(largest_sum, sum);
}
}
return largest_sum;
}
After obtaining the different row sums for each group, the sum variable is reset, with
int sum = 0;just before the group iteration begins (again). Notice that there is no need for subtraction of prefix sums, because the inner for-loop here, does addition for a slice, and not for the whole range. In fact, each slice sum constitutes a prefix sums difference.
Solution with O(n) time complexity
There is an algorithm called Kadane’s algorithm that solves the maximum slice problem in O(n) time. The information in this section of the tutorial (lesson) is not the original work from Kadane. It is the author’s own way to teach Kadane’s algorithm.The Running Total is the sum of all the numbers one-by-one, from the start of the list onwards. If all the numbers in the list are positive, then the maximum slice sum is the sum of all the numbers in the list. In this case, the maximum slice sum is the running total for the whole list. In the Code for Kadane’s Algorithm below, the running total is actually the variable, accumulatingMaxSum.
Trouble starts when there are negative numbers in different parts of the whole list. In that case, it is possible for the running total (accumulatingMaxSum) to become negative in different parts, as the list is scanned from the start to the end.
If the continuous running total is plotted in a graph against indexes, for the whole list, then there may be several peaks of running totals (accumulatingMaxSum). The highest of these peaks is an indication of the maximum slice sum.
In practice, running total (accumulatingMaxSum) is not calculated continuously from the start to the end of the list. It is calculated as groups of consecutive numbers in the list. Do not forget that the maximum slice sum is from a group of consecutive numbers. Each group of running total (accumulatingMaxSum) has its own peak value. Accept without proof here, that the highest of these peaks is the maximum slice sum. The reader should consult some other document for the proof. So in one scan of the list, the highest peak can be found.
Also accept without proof, that the sequence for the addition of running total (accumulatingMaxSum) for a group, starts at the index, whose value is higher than the value of the previous running total. The reader should consult some other document for the proof. The previous addition sequence of running total ends at the index just before this new index. Read the code below for clarification.
Code for Kadane’s Algorithm in C
The code given in this lesson (tutorial) is not necessarily what Kadane used. However, it is by his algorithm. The program like many other C programs, would begin with:
#include <stdio.h>
There is inclusion of the iostream library, which is responsible for input and output. The standard namespace is used. The idea of Kadane’s algorithm is to be having the running total while comparing the maximum sums as they are encountered, moving from left to right in the given array. The function for the algorithm is (read the code and comments):
int maxSunArray(int A[], int N) {
int prevMaxSum = A[0]; //previous peak
int accumulatingMaxSum = A[0];
for (int i=1; i < N; i++) {
int tempRunTotal = accumulatingMaxSum + A[i]; //could be same or smaller than A[i]
if (A[i] > tempRunTotal)
accumulatingMaxSum = A[i]; //new running total starts
else
accumulatingMaxSum = tempRunTotal; //continue to accumulate current running total
if (accumulatingMaxSum > prevMaxSum) //comparing all the previous peaks with current possible peak
prevMaxSum = accumulatingMaxSum;
}
return prevMaxSum; //at end of list
}
Note that the scanning begins from i = 1 and not i = 0. The variables, accumulatingMaxSum and tempRunTotal work together to determine when the elements in the given array start rising.This function is applicable to the case where all the numbers in the given array are negative. When all the numbers in the list are negative, only the highest number at one index, is the maximum slice sum. Remember that the sum of at least two negative numbers, is lower than the lowest of the negative numbers. The statement, "accumulatingMaxSum = A[i];" is what locates the highest negative number, when all the numbers in the list are negative.
The content for a suitable C main() function, for the Kadane’s algorithm function is:
int main(int argc, char **argv)
{
int A[] = {5, -7, 3, 5, -2, 4, -1}; // {3, 5, -2, 4} -> 10
int N = sizeof(A)/sizeof(A[0]); //size of array divided by size of one (first) element
int ret1 = maxSunArray(A, N);
printf("%i\n", ret1);
int B[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4}; // {4, −1, 2, 1} -> 6
N = sizeof(B)/sizeof(B[0]);
int ret2 = maxSunArray(B, N);
printf("%i\n", ret2);
int C[] = {3, 2, -6, 4, 0}; //{3, 2} -> 5
N = sizeof(C)/sizeof(C[0]);
int ret3 = maxSunArray(C, N);
printf("%i\n", ret3);
int D[] = {3, 2, 6, -1, 4, 5, -1, 2}; //{3, 2, 6, -1, 4, 5, -1, 2} -> 20
N = sizeof(D)/sizeof(D[0]);
int ret4 = maxSunArray(D, N);
printf("%i\n", ret4);
int E[] = {5, 7, -4, -10, -6, 6, 5, 10, -5, 15, 4, -8, -15, -22}; // {6, 5, 10, -5, 15, 4}->35
N = sizeof(E)/sizeof(E[0]);
int ret5 = maxSunArray(E, N);
printf("%i\n", ret5);
int F[] = {-4, 10, 15, 9, -5, -20, -3, -12, -3, 4, 6, 3, 2, 8, 3, -5, -2}; // {10, 15, 9}->34
N = sizeof(F)/sizeof(F[0]);
int ret6 = maxSunArray(F, N);
printf("%i\n", ret6);
return 0;
}
With that, the output will be:10
6
5
20
35
34
Each answer in a line here, corresponds to a given array, in order.
Conclusion
There can be more than one maximum sum, for different possible sub-arrays. The highest maximum sum, for all the possible sub-arrays, will be chosen. Kadane’s algorithm achieves this in O(n) time with running totals for the sub-arrays.Chrys