MaxSliceSum at app.codility.com/programmers in Go 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:
func Solution(A []int) intthat, 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):
package main
import (
"fmt";
)
func Solution(A []int) int {
var N = len(A);
var prevMaxSum int = A[0];
var accumulatingMaxSum int = A[0];
for i:=1; i < N; i++ {
var tempRunTotal int = 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;
}
func main() {
var A = []int{5, -7, 3, 5, -2, 4, -1}; // {3, 5, -2, 4} -> 10
var ret1 int = Solution(A);
fmt.Println(ret1);
var B = []int{-2, 1, -3, 4, -1, 2, 1, -5, 4}; // {4, −1, 2, 1} -> 6
var ret2 int = Solution(B);
fmt.Println(ret2);
var C = []int{3, 2, -6, 4, 0}; //{3, 2} -> 5
var ret3 int = Solution(C);
fmt.Println(ret3);
var D = []int{3, 2, 6, -1, 4, 5, -1, 2}; //{3, 2, 6, -1, 4, 5, -1, 2} -> 20
var ret4 int = Solution(D);
fmt.Println(ret4);
var E = []int{5, 7, -4, -10, -6, 6, 5, 10, -5, 15, 4, -8, -15, -22}; // {6, 5, 10, -5, 15, 4}->35
var ret5 int = Solution(E);
fmt.Println(ret5);
var F = []int{-4, 10, 15, 9, -5, -20, -3, -12, -3, 4, 6, 3, 2, 8, 3, -5, -2}; // {10, 15, 9}->34
var ret6 int = Solution(F);
fmt.Println(ret6);
}
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)
Remember that at app.codility.com, the Go main function is not typed (not submitted). Before submitting, also delete '"fmt";' and replace "package main" with "package solution".
Thanks for reading.