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:
class Solution { public int solution(int[] 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 Java 8
Time spent on task 34 minutes
Notes
not defined yet
Task timeline
Code: 00:30:33 UTC,
java,
verify,
result: Failed
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
import java.lang.Math;
class Solution {
public int solution(int[] A) {
// write your code in Java SE 8
if(A.length < 4)
return 0;
int maxleft=0, maxending=0, maxslice=0;
for(int i=3; i<A.length; i++) {
maxleft = Math.max(maxleft+A[i-2], A[i-2]);
maxending = Math.max(maxleft, A[i-1], maxending+A[i-1]);
maxslice = Math.max(maxending, maxslice);
}
return maslice;
}
}
Analysis
Compile error
Solution.java:15: error: no suitable method found for max(int,int,int)
maxending = Math.max(maxleft, A[i-1], maxending+A[i-1]);
^
method Math.max(int,int) is not applicable
(actual and formal argument lists differ in length)
method Math.max(long,long) is not applicable
(actual and formal argument lists differ in length)
method Math.max(float,float) is not applicable
(actual and formal argument lists differ in length)
method Math.max(double,double) is not applicable
(actual and formal argument lists differ in length)
Solution.java:18: error: cannot find symbol
return maslice;
^
symbol: variable maslice
location: class Solution
2 errors
Code: 00:31:00 UTC,
java,
verify,
result: Failed
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
import java.lang.Math;
class Solution {
public int solution(int[] A) {
// write your code in Java SE 8
if(A.length < 4)
return 0;
int maxleft=0, maxending=0, maxslice=0;
for(int i=3; i<A.length; i++) {
maxleft = Math.max(maxleft+A[i-2], A[i-2]);
maxending = Math.max(maxleft, Math.max( A[i-1], maxending+A[i-1]));
maxslice = Math.max(maxending, maxslice);
}
return maslice;
}
}
Analysis
Compile error
Solution.java:18: error: cannot find symbol
return maslice;
^
symbol: variable maslice
location: class Solution
1 error
Code: 00:31:07 UTC,
java,
verify,
result: Passed
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
import java.lang.Math;
class Solution {
public int solution(int[] A) {
// write your code in Java SE 8
if(A.length < 4)
return 0;
int maxleft=0, maxending=0, maxslice=0;
for(int i=3; i<A.length; i++) {
maxleft = Math.max(maxleft+A[i-2], A[i-2]);
maxending = Math.max(maxleft, Math.max( A[i-1], maxending+A[i-1]));
maxslice = Math.max(maxending, maxslice);
}
return maxslice;
}
}
Analysis
Code: 00:31:17 UTC,
java,
verify,
result: Passed
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
import java.lang.Math;
class Solution {
public int solution(int[] A) {
// write your code in Java SE 8
if(A.length < 4)
return 0;
int maxleft=0, maxending=0, maxslice=0;
for(int i=3; i<A.length; i++) {
maxleft = Math.max(maxleft+A[i-2], A[i-2]);
maxending = Math.max(maxleft, Math.max( A[i-1], maxending+A[i-1]));
maxslice = Math.max(maxending, maxslice);
}
return maxslice;
}
}
Analysis
Code: 00:31:25 UTC,
java,
final,
score:
100
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
import java.lang.Math;
class Solution {
public int solution(int[] A) {
// write your code in Java SE 8
if(A.length < 4)
return 0;
int maxleft=0, maxending=0, maxslice=0;
for(int i=3; i<A.length; i++) {
maxleft = Math.max(maxleft+A[i-2], A[i-2]);
maxending = Math.max(maxleft, Math.max( A[i-1], maxending+A[i-1]));
maxslice = Math.max(maxending, maxslice);
}
return maxslice;
}
}Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(N)
expand all
Correctness tests
1.
0.141 s
OK
2.
0.089 s
OK
3.
0.032 s
OK
1.
0.120 s
OK
2.
0.052 s
OK
1.
0.065 s
OK
1.
0.054 s
OK
1.
0.032 s
OK
1.
0.029 s
OK
expand all
Performance tests
1.
0.031 s
OK
1.
0.039 s
OK
1.
0.046 s
OK
1.
0.477 s
OK
1.
0.639 s
OK
1.
0.716 s
OK
1.
0.635 s
OK
2.
0.450 s
OK