Test results - Codility

Tasks Details

easy

1. MaxSliceSum

Find a maximum sum of a compact subsequence of array elements.

100%

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,

(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).

Write an efficient algorithm for the following assumptions:

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].

Solution

Programming language used C++

Time spent on task 1 minutes

Notes

not defined yet

Task timeline

Code: 06:07:17 UTC, cpp, verify, result: Passed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

// you can use includes, for example:
#include <bits/stdc++.h>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

int solution(vector<int> &A) {
    int len = A.size();
    int max_sum = A[0];
    int cur_sum = A[0];
    if(len == 1){
        return A[0];
    }
    // write your code in C++14 (g++ 6.2.0)
    for(int i=1; i<len; i++){
        cur_sum = max(A[i], cur_sum+A[i]);
        max_sum = max(max_sum, cur_sum);
    }

    return max_sum;
}

Analysis

▶

example

✔

Code: 06:07:23 UTC, cpp, verify, result: Passed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

// you can use includes, for example:
#include <bits/stdc++.h>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

int solution(vector<int> &A) {
    int len = A.size();
    int max_sum = A[0];
    int cur_sum = A[0];
    if(len == 1){
        return A[0];
    }
    // write your code in C++14 (g++ 6.2.0)
    for(int i=1; i<len; i++){
        cur_sum = max(A[i], cur_sum+A[i]);
        max_sum = max(max_sum, cur_sum);
    }

    return max_sum;
}

Analysis

▶

example

✔

Code: 06:07:31 UTC, cpp, verify, result: Passed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

// you can use includes, for example:
#include <bits/stdc++.h>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

int solution(vector<int> &A) {
    int len = A.size();
    int max_sum = A[0];
    int cur_sum = A[0];
    if(len == 1){
        return A[0];
    }
    // write your code in C++14 (g++ 6.2.0)
    for(int i=1; i<len; i++){
        cur_sum = max(A[i], cur_sum+A[i]);
        max_sum = max(max_sum, cur_sum);
    }

    return max_sum;
}

Analysis

▶

example

✔

Code: 06:07:36 UTC, cpp, final, score: 100

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

// you can use includes, for example:
#include <bits/stdc++.h>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

int solution(vector<int> &A) {
    int len = A.size();
    int max_sum = A[0];
    int cur_sum = A[0];
    if(len == 1){
        return A[0];
    }
    // write your code in C++14 (g++ 6.2.0)
    for(int i=1; i<len; i++){
        cur_sum = max(A[i], cur_sum+A[i]);
        max_sum = max(max_sum, cur_sum);
    }

    return max_sum;
}

Analysis summary

The solution obtained perfect score.

Analysis

Detected time complexity:

O(N)

▶

example

✔

▶

one_element

✔

▶

two_elements

✔

0.001 s

▶

three_elements

✔

▶

simple

✔

▶

extreme_minimum

✔

▶

fifty_random

✔

▶

neg_const

✔

▶

pos_const

✔

▶

high_low_1Kgarbage

✔

▶

1Kgarbage_high_low

✔

▶

growing_saw

✔

▶

blocks

✔

▶

growing_negative

✔