MaxSliceSum at app.codility.com/programmers in C Explained: Find a maximum sum of a compact subsequence of array elements.
Task score : 100% - Correctness : 100% ; Performance : 100%
Detected time complexity : O(N)
Lesson 9 at app.codility.com/programmers
The solution and its explanation are given below.
Category of Article : Technology | Computers and Software | Algorithm
By: Chrysanthus Date Published: 30 Jul 2025
Problem
A non-empty array A consisting of N integers is given. A pair of integers (P, Q), such that 0 ≤ P ≤ Q < N, is called a slice of array A. The sum of a slice (P, Q) is the total of A[P] + A[P+1] + ... + A[Q].Write a function:
int solution(int A[], int N);that, given an array A consisting of N integers, returns the maximum sum of any slice of A.
For example, given array A such that:
A[0] = 3 A[1] = 2 A[2] = -6
A[3] = 4 A[4] = 0
the function should return 5 because:
(3, 4) is a slice of A that has sum 4,Write an efficient algorithm for the following assumptions:
(2, 2) is a slice of A that has sum -6,
(0, 1) is a slice of A that has sum 5,
no other slice of A has sum greater than (0, 1).
• N is an integer within the range [1..1,000,000];
• each element of array A is an integer within the range [−1,000,000..1,000,000];
• the result will be an integer within the range [−2,147,483,648..2,147,483,647].
Strategy
This needs direct application of Kadane’s algorithm. It is assumed that the reader has read the lesson for this problem which is on Maximum Slice Problem. It is also assumed that the reader has done the previous test on MaxProfit.Smart Solution
The solution() function is in the following program (read the code and comments):
#include <stdio.h>
int solution(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
}
int main()
{
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 = solution(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 = solution(B, N);
printf("%i\n", ret2);
int C[] = {3, 2, -6, 4, 0}; //{3, 2} -> 5
N = sizeof(C)/sizeof(C[0]);
int ret3 = solution(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 = solution(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 = solution(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 = solution(F, N);
printf("%i\n", ret6);
return 0;
}
The output is:10
6
5
20
35
34
At app.codility.com/programmers the scoring and detected time complexity for this solution() is:
Task score : 100% - Correctness : 100% ; Performance : 100%
Detected time complexity : O(N)
Thanks for reading.