Tasks Details
medium
Find the maximal sum of any double slice.
Task Score
100%
Correctness
100%
Performance
100%
A non-empty array A consisting of N integers is given.
A triplet (X, Y, Z), such that 0 ≤ X < Y < Z < N, is called a double slice.
The sum of double slice (X, Y, Z) is the total of A[X + 1] + A[X + 2] + ... + A[Y − 1] + A[Y + 1] + A[Y + 2] + ... + A[Z − 1].
For example, array A such that:
A[0] = 3 A[1] = 2 A[2] = 6 A[3] = -1 A[4] = 4 A[5] = 5 A[6] = -1 A[7] = 2contains the following example double slices:
- double slice (0, 3, 6), sum is 2 + 6 + 4 + 5 = 17,
- double slice (0, 3, 7), sum is 2 + 6 + 4 + 5 − 1 = 16,
- double slice (3, 4, 5), sum is 0.
The goal is to find the maximal sum of any double slice.
Write a function:
def solution(A)
that, given a non-empty array A consisting of N integers, returns the maximal sum of any double slice.
For example, given:
A[0] = 3 A[1] = 2 A[2] = 6 A[3] = -1 A[4] = 4 A[5] = 5 A[6] = -1 A[7] = 2the function should return 17, because no double slice of array A has a sum of greater than 17.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [3..100,000];
- each element of array A is an integer within the range [−10,000..10,000].
Copyright 2009–2024 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used Python
Total time used 25 minutes
Effective time used 25 minutes
Notes
not defined yet
Task timeline
Code: 15:58:27 UTC,
java,
autosave
Code: 15:58:45 UTC,
py,
autosave
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
fromStartMaxEnding = [0] * len(A)
for i in range(1, len(A)-1):
fromStartMaxEnding[i] = max(fromStartMaxEnding[i-1], fromStartMaxEnding[i-1]+A[i])
fromEndMaxEnding = [0] * len(A)
for i in range(len(A)-2, 0, -1):
fromEndMaxEnding[i] = max(fromEndMaxEnding[i+1], fromEndMaxEnding[i+1]+A[i])
ans = -1 * 2**23
for i in range(1, len(A)-1):
ans = max(ans, fromStartMaxEnding[i-1] + fromEndMaxEnding[i+1])
return ans
Code: 15:59:05 UTC,
py,
autosave
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
fromStartMaxEnding = [0] * len(A)
for i in range(1, len(A)-1):
fromStartMaxEnding[i] = max(fromStartMaxEnding[i-1], fromStartMaxEnding[i-1]+A[i])
print
fromEndMaxEnding = [0] * len(A)
for i in range(len(A)-2, 0, -1):
fromEndMaxEnding[i] = max(fromEndMaxEnding[i+1], fromEndMaxEnding[i+1]+A[i])
ans = -1 * 2**23
for i in range(1, len(A)-1):
ans = max(ans, fromStartMaxEnding[i-1] + fromEndMaxEnding[i+1])
return ans
Code: 15:59:15 UTC,
py,
autosave
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
fromStartMaxEnding = [0] * len(A)
for i in range(1, len(A)-1):
fromStartMaxEnding[i] = max(fromStartMaxEnding[i-1], fromStartMaxEnding[i-1]+A[i])
print()
fromEndMaxEnding = [0] * len(A)
for i in range(len(A)-2, 0, -1):
fromEndMaxEnding[i] = max(fromEndMaxEnding[i+1], fromEndMaxEnding[i+1]+A[i])
ans = -1 * 2**23
for i in range(1, len(A)-1):
ans = max(ans, fromStartMaxEnding[i-1] + fromEndMaxEnding[i+1])
return ans
Code: 15:59:29 UTC,
py,
autosave
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
fromStartMaxEnding = [0] * len(A)
for i in range(1, len(A)-1):
fromStartMaxEnding[i] = max(fromStartMaxEnding[i-1], fromStartMaxEnding[i-1]+A[i])
print(fromStartMaxEnding[i])
fromEndMaxEnding = [0] * len(A)
for i in range(len(A)-2, 0, -1):
fromEndMaxEnding[i] = max(fromEndMaxEnding[i+1], fromEndMaxEnding[i+1]+A[i])
print()
ans = -1 * 2**23
for i in range(1, len(A)-1):
ans = max(ans, fromStartMaxEnding[i-1] + fromEndMaxEnding[i+1])
return ans
Code: 15:59:34 UTC,
py,
verify,
result: Passed
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
fromStartMaxEnding = [0] * len(A)
for i in range(1, len(A)-1):
fromStartMaxEnding[i] = max(fromStartMaxEnding[i-1], fromStartMaxEnding[i-1]+A[i])
print(fromStartMaxEnding[i])
fromEndMaxEnding = [0] * len(A)
for i in range(len(A)-2, 0, -1):
fromEndMaxEnding[i] = max(fromEndMaxEnding[i+1], fromEndMaxEnding[i+1]+A[i])
print(fromEndMaxEnding[i])
ans = -1 * 2**23
for i in range(1, len(A)-1):
ans = max(ans, fromStartMaxEnding[i-1] + fromEndMaxEnding[i+1])
return ans
Analysis
expand all
Example tests
1.
0.036 s
OK
stdout:
2 8 8 12 17 17 0 5 9 9 15 17
Code: 16:00:14 UTC,
py,
verify,
result: Passed
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
fromStartMaxEnding = [0] * len(A)
for i in range(1, len(A)-1):
fromStartMaxEnding[i] = max(fromStartMaxEnding[i-1], fromStartMaxEnding[i-1]+A[i])
print(fromStartMaxEnding[i])
fromEndMaxEnding = [0] * len(A)
for i in range(len(A)-2, 0, -1):
fromEndMaxEnding[i] = max(fromEndMaxEnding[i+1], fromEndMaxEnding[i+1]+A[i])
print(fromEndMaxEnding[i])
ans = -1 * 2**23
for i in range(1, len(A)-1):
ans = max(ans, fromStartMaxEnding[i-1] + fromEndMaxEnding[i+1])
return ans
User test case 1:
[1, -2, 3, -4, -5]
Analysis
expand all
Example tests
1.
0.036 s
OK
stdout:
2 8 8 12 17 17 0 5 9 9 15 17
Code: 16:01:12 UTC,
py,
verify,
result: Passed
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
fromStartMaxEnding = [0] * len(A)
for i in range(1, len(A)-1):
fromStartMaxEnding[i] = max(fromStartMaxEnding[i-1], fromStartMaxEnding[i-1]+A[i])
print(fromStartMaxEnding[i])
fromEndMaxEnding = [0] * len(A)
for i in range(len(A)-2, 0, -1):
fromEndMaxEnding[i] = max(fromEndMaxEnding[i+1], fromEndMaxEnding[i+1]+A[i])
print(fromEndMaxEnding[i])
ans = -1 * 2**23
for i in range(1, len(A)-1):
ans = max(ans, fromStartMaxEnding[i-1] + fromEndMaxEnding[i+1])
return ans
User test case 1:
[-1, -2, -3, -4, -5]
Analysis
expand all
Example tests
1.
0.052 s
OK
stdout:
2 8 8 12 17 17 0 5 9 9 15 17
Code: 16:04:42 UTC,
py,
autosave
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
fromStartMaxEnding = [0] * len(A)
for i in range(1, len(A)-1):
fromStartMaxEnding[i] = max(fromStartMaxEnding[i-1], fromStartMaxEnding[i-1]+A[i])
print(fromStartMaxEnding[i])
fromEndMaxEnding = [0] * len(A)
for i in range(len(A)-2, 0, -1):
fromEndMaxEnding[i] = max(0, fromEndMaxEnding[i+1]+A[i])
print(fromEndMaxEnding[i])
ans = -1 * 2**23
for i in range(1, len(A)-1):
ans = max(ans, fromStartMaxEnding[i-1] + fromEndMaxEnding[i+1])
return ans
Code: 16:04:48 UTC,
py,
verify,
result: Passed
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
fromStartMaxEnding = [0] * len(A)
for i in range(1, len(A)-1):
fromStartMaxEnding[i] = max(0, fromStartMaxEnding[i-1]+A[i])
print(fromStartMaxEnding[i])
fromEndMaxEnding = [0] * len(A)
for i in range(len(A)-2, 0, -1):
fromEndMaxEnding[i] = max(0, fromEndMaxEnding[i+1]+A[i])
print(fromEndMaxEnding[i])
ans = -1 * 2**23
for i in range(1, len(A)-1):
ans = max(ans, fromStartMaxEnding[i-1] + fromEndMaxEnding[i+1])
return ans
User test case 1:
[-1, -2, -3, -4, -5]
Analysis
expand all
Example tests
1.
0.036 s
OK
stdout:
2 8 7 11 16 15 0 5 9 8 14 16
Code: 16:05:53 UTC,
py,
verify,
result: Passed
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
fromStartMaxEnding = [0] * len(A)
for i in range(1, len(A)-1):
fromStartMaxEnding[i] = max(0, fromStartMaxEnding[i-1]+A[i])
print(fromStartMaxEnding[i])
fromEndMaxEnding = [0] * len(A)
for i in range(len(A)-2, 0, -1):
fromEndMaxEnding[i] = max(0, fromEndMaxEnding[i+1]+A[i])
print(fromEndMaxEnding[i])
ans = -1 * 2**23
for i in range(1, len(A)-1):
ans = max(ans, fromStartMaxEnding[i-1] + fromEndMaxEnding[i+1])
return ans
User test case 1:
[-1, -2, -3, -4, -5]
Analysis
expand all
Example tests
1.
0.036 s
OK
stdout:
2 8 7 11 16 15 0 5 9 8 14 16
Code: 16:05:59 UTC,
py,
autosave
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
fromStartMaxEnding = [0] * len(A)
for i in range(1, len(A)-1):
fromStartMaxEnding[i] = max(0, fromStartMaxEnding[i-1]+A[i])
print(fromStartMaxEnding[i])
fromEndMaxEnding = [0] * len(A)
for i in range(len(A)-2, 0, -1):
fromEndMaxEnding[i] = max(0, fromEndMaxEnding[i+1]+A[i])
ans = -1 * 2**23
for i in range(1, len(A)-1):
ans = max(ans, fromStartMaxEnding[i-1] + fromEndMaxEnding[i+1])
return ans
Code: 16:06:10 UTC,
py,
autosave
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
fromStartMaxEnding = [0] * len(A)
for i in range(1, len(A)-1):
fromStartMaxEnding[i] = max(0, fromStartMaxEnding[i-1]+A[i])
fromEndMaxEnding = [0] * len(A)
for i in range(len(A)-2, 0, -1):
fromEndMaxEnding[i] = max(0, fromEndMaxEnding[i+1]+A[i])
ans = -1 * 2**23
for i in range(1, len(A)-1):
ans = max(ans, fromStartMaxEnding[i-1] + fromEndMaxEnding[i+1])
return ans
Code: 16:22:27 UTC,
py,
verify,
result: Passed
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
fromStartMaxEnding = [0] * len(A)
for i in range(1, len(A)-1):
fromStartMaxEnding[i] = max(0, fromStartMaxEnding[i-1]+A[i])
fromEndMaxEnding = [0] * len(A)
for i in range(len(A)-2, 0, -1):
fromEndMaxEnding[i] = max(0, fromEndMaxEnding[i+1]+A[i])
ans = -1 * 2**23
for i in range(1, len(A)-1):
ans = max(ans, fromStartMaxEnding[i-1] + fromEndMaxEnding[i+1])
return ans
User test case 1:
[-1, -2, -3, -4, -5]
Analysis
Code: 16:22:29 UTC,
py,
final,
score:
100
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
fromStartMaxEnding = [0] * len(A)
for i in range(1, len(A)-1):
fromStartMaxEnding[i] = max(0, fromStartMaxEnding[i-1]+A[i])
fromEndMaxEnding = [0] * len(A)
for i in range(len(A)-2, 0, -1):
fromEndMaxEnding[i] = max(0, fromEndMaxEnding[i+1]+A[i])
ans = -1 * 2**23
for i in range(1, len(A)-1):
ans = max(ans, fromStartMaxEnding[i-1] + fromEndMaxEnding[i+1])
return ansAnalysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(N)
expand all
Correctness tests
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
1.
0.036 s
OK
2.
0.036 s
OK
1.
0.036 s
OK
1.
0.036 s
OK
1.
0.036 s
OK
1.
0.036 s
OK
expand all
Performance tests
1.
0.036 s
OK
1.
0.036 s
OK
1.
0.040 s
OK
1.
0.236 s
OK
1.
0.248 s
OK
1.
0.264 s
OK
1.
0.248 s
OK
2.
0.236 s
OK