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(vector<int> &A);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 <iostream>The output is:
#include<vector>
using namespace std;
int solution(vector<int> &A) {
int N = A.size();
int prevMaxSum = A[0];
int accumulatingMaxSum = A[0];
for (int i=1; i < N; i++) {
int tempRunTotal = accumulatingMaxSum + A[i]; //could be smaller than A[i]
if (A[i] > tempRunTotal)
accumulatingMaxSum = A[i]; //elements start rising
else
accumulatingMaxSum = tempRunTotal; //continue to accumulate
if (accumulatingMaxSum > prevMaxSum) //comparing all the maximum sums
prevMaxSum = accumulatingMaxSum;
}
return prevMaxSum;
}
int main()
{
vector<int> A = {5, -7, 3, 5, -2, 4, -1}; // {3, 5, -2, 4} -> 10
int ret1 = solution(A);
cout << ret1 << endl;
vector<int> B = {-2, 1, -3, 4, -1, 2, 1, -5, 4}; // {4, −1, 2, 1} -> 6
int ret2 = solution(B);
cout << ret2 << endl;
vector<int> C = {3, 2, -6, 4, 0}; //{3, 2} -> 5
int ret3 = solution(C);
cout << ret3 << endl;
vector<int> D = {3, 2, 6, -1, 4, 5, -1, 2}; //{3, 2, 6, -1, 4, 5, -1, 2} -> 20
int ret4 = solution(D);
cout << ret4 << endl;
vector<int> E = {5, 7, -4, -10, -6, 6, 5, 10, -5, 15, 4, -8, -15, -22}; // {6, 5, 10, -5, 15, 4}->35
int ret5 = solution(E);
cout << ret5 << endl;
vector<int> F = {-4, 10, 15, 9, -5, -20, -3, -12, -3, 4, 6, 3, 2, 8, 3, -5, -2}; // {10, 15, 9}->34
int ret6 = solution(F);
cout << ret6 << endl;
return 0;
}
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.