Test results - Codility

Tasks Details

hard

1. MaxSliceSwap

Find the maximum sum of a compact subsequence of array elements after performing a single swap operation.

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]. The maximum sum is the maximum sum of any slice of A.

For example, consider array A such that:

A[0] = 3 A[1] = 2 A[2] = -6 A[3] = 3 A[4] = 1

For example (0, 1) is a slice of A that has sum A[0] + A[1] = 5. This is the maximum sum of A.

You can perform a single swap operation in array A. This operation takes two indices I and J, such that 0 ≤ I ≤ J < N, and exchanges the values of A[I] and A[J]. The goal is to find the maximum sum you can achieve after performing a single swap.

For example, after swapping elements 2 and 4, you will get the following array A:

A[0] = 3 A[1] = 2 A[2] = 1 A[3] = 3 A[4] = -6

After that, (0, 3) is a slice of A that has the sum A[0] + A[1] + A[2] + A[3] = 9. This is the maximum possible sum of A after a single swap.

Write a function:

int solution(vector<int> &A);

that, given a non-empty array A of N integers, returns the maximum possible sum of any slice of A after a single swap operation.

For example, given:

A[0] = 3 A[1] = 2 A[2] = -6 A[3] = 3 A[4] = 1

the function should return 9, as explained above.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..100,000];

each element of array A is an integer within the range [−10,000..10,000].

Solution

Programming language used C++

Time spent on task 12 minutes

Notes

not defined yet

Task timeline

Code: 13:52:10 UTC, cpp, verify, result: Failed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

// you can also use includes, for example:
#include <algorithm>

int help(vector<int> &a) {
    int n = a.size();
    vector<int> f,g;
    f.resize(n);
    f[0] = a[0];
    int now = a[0];
    for (int i = 1; i < n; ++i) {
        now = max(now, a[i]);
        f[i] = max(a[i] + f[i - 1], now);
    }
    g.resize(n);
    g[n - 1] = A[n - 1];
    int answer = A[n - 1];
    for (int i = n - 2; i >= 0; --i) {
        g[i] = max(g[i + 1, 0) + a[i];
        answer = max(answer, g[i]);
    }
    for (int i = 1; i < n; ++i) {
        answer = max(answer, g[i] - a[i] + f[i - 1]);
    }
    return answer;
}

int solution(vector<int> &A) {
    // write your code in C++11
    int answer = help(A);
    for (int i = 0, j = A.size() - 1; i < j; ++i,--j) {
        swap(A[i],A[j]);
    }
    answer = max(answer,help(A));
    return answer;
    
}

Analysis

Compile error

In file included from user.cpp:20:0:
func.cpp: In function 'int help(std::vector<int>&)':
func.cpp:15:16: error: 'A' was not declared in this scope
     g[n - 1] = A[n - 1];
                ^
func.cpp:18:24: warning: left operand of comma operator has no effect [-Wunused-value]
         g[i] = max(g[i + 1, 0) + a[i];
                        ^
func.cpp:18:30: error: expected ']' before ')' token
         g[i] = max(g[i + 1, 0) + a[i];
                              ^
func.cpp:18:30: error: no matching function for call to 'max(__gnu_cxx::__alloc_traits<std::allocator<int> >::value_type&)'
func.cpp:18:30: note: candidates are:
In file included from /usr/include/c++/4.8/bits/char_traits.h:39:0,
                 from /usr/include/c++/4.8/string:40,
                 from user.cpp:4:
/usr/include/c++/4.8/bits/stl_algobase.h:216:5: note: template<class _Tp> const _Tp& std::max(const _Tp&, const _Tp&)
     max(const _Tp& __a, const _Tp& __b)
     ^
/usr/include/c++/4.8/bits/stl_algobase.h:216:5: note:   template argument deduction/substitution failed:
In file included from user.cpp:20:0:
func.cpp:18:30: note:   candidate expects 2 arguments, 1 provided
         g[i] = max(g[i + 1, 0) + a[i];
                              ^
In file included from /usr/include/c++/4.8/bits/char_traits.h:39:0,
                 from /usr/include/c++/4.8/string:40,
                 from user.cpp:4:
/usr/include/c++/4.8/bits/stl_algobase.h:260:5: note: template<class _Tp, class _Compare> const _Tp& std::max(const _Tp&, const _Tp&, _Compare)
     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
     ^
/usr/include/c++/4.8/bits/stl_algobase.h:260:5: note:   template argument deduction/substitution failed:
In file included from user.cpp:20:0:
func.cpp:18:30: note:   candidate expects 3 arguments, 1 provided
         g[i] = max(g[i + 1, 0) + a[i];
                              ^
In file included from /usr/include/c++/4.8/algorithm:62:0,
                 from func.cpp:2,
                 from user.cpp:20:
/usr/include/c++/4.8/bits/stl_algo.h:4254

Code: 13:52:54 UTC, cpp, verify, result: Failed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

// you can also use includes, for example:
#include <algorithm>

int help(vector<int> &a) {
    int n = a.size();
    vector<int> f,g;
    f.resize(n);
    f[0] = a[0];
    int now = a[0];
    for (int i = 1; i < n; ++i) {
        now = max(now, a[i]);
        f[i] = max(a[i] + f[i - 1], now);
    }
    g.resize(n);
    g[n - 1] = a[n - 1];
    int answer = a[n - 1];
    for (int i = n - 2; i >= 0; --i) {
        g[i] = max(g[i + 1, 0) + a[i];
        answer = max(answer, g[i]);
    }
    for (int i = 1; i < n; ++i) {
        answer = max(answer, g[i] - a[i] + f[i - 1]);
    }
    return answer;
}

int solution(vector<int> &A) {
    // write your code in C++11
    int answer = help(A);
    for (int i = 0, j = A.size() - 1; i < j; ++i,--j) {
        swap(A[i],A[j]);
    }
    answer = max(answer,help(A));
    return answer;
    
}

Analysis

Compile error

In file included from user.cpp:20:0:
func.cpp: In function 'int help(std::vector<int>&)':
func.cpp:18:24: warning: left operand of comma operator has no effect [-Wunused-value]
         g[i] = max(g[i + 1, 0) + a[i];
                        ^
func.cpp:18:30: error: expected ']' before ')' token
         g[i] = max(g[i + 1, 0) + a[i];
                              ^
func.cpp:18:30: error: no matching function for call to 'max(__gnu_cxx::__alloc_traits<std::allocator<int> >::value_type&)'
func.cpp:18:30: note: candidates are:
In file included from /usr/include/c++/4.8/bits/char_traits.h:39:0,
                 from /usr/include/c++/4.8/string:40,
                 from user.cpp:4:
/usr/include/c++/4.8/bits/stl_algobase.h:216:5: note: template<class _Tp> const _Tp& std::max(const _Tp&, const _Tp&)
     max(const _Tp& __a, const _Tp& __b)
     ^
/usr/include/c++/4.8/bits/stl_algobase.h:216:5: note:   template argument deduction/substitution failed:
In file included from user.cpp:20:0:
func.cpp:18:30: note:   candidate expects 2 arguments, 1 provided
         g[i] = max(g[i + 1, 0) + a[i];
                              ^
In file included from /usr/include/c++/4.8/bits/char_traits.h:39:0,
                 from /usr/include/c++/4.8/string:40,
                 from user.cpp:4:
/usr/include/c++/4.8/bits/stl_algobase.h:260:5: note: template<class _Tp, class _Compare> const _Tp& std::max(const _Tp&, const _Tp&, _Compare)
     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
     ^
/usr/include/c++/4.8/bits/stl_algobase.h:260:5: note:   template argument deduction/substitution failed:
In file included from user.cpp:20:0:
func.cpp:18:30: note:   candidate expects 3 arguments, 1 provided
         g[i] = max(g[i + 1, 0) + a[i];
                              ^
In file included from /usr/include/c++/4.8/algorithm:62:0,
                 from func.cpp:2,
                 from user.cpp:20:
/usr/include/c++/4.8/bits/stl_algo.h:4254:5: note: template<class _Tp> _Tp std::max(std::initializer_list<_Tp>)
     max(initializer_list<_Tp>

Code: 13:53:23 UTC, cpp, verify, result: Failed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

// you can also use includes, for example:
#include <algorithm>

int help(vector<int> &a) {
    int n = a.size();
    vector<int> f,g;
    f.resize(n);
    f[0] = a[0];
    int now = a[0];
    for (int i = 1; i < n; ++i) {
        now = max(now, a[i]);
        f[i] = max(a[i] + f[i - 1], now);
    }
    g.resize(n);
    g[n - 1] = a[n - 1];
    int answer = a[n - 1];
    for (int i = n - 2; i >= 0; --i) {
        g[i] = max(g[i + 1］, 0) + a[i];
        answer = max(answer, g[i]);
    }
    for (int i = 1; i < n; ++i) {
        answer = max(answer, g[i] - a[i] + f[i - 1]);
    }
    return answer;
}

int solution(vector<int> &A) {
    // write your code in C++11
    int answer = help(A);
    for (int i = 0, j = A.size() - 1; i < j; ++i,--j) {
        swap(A[i],A[j]);
    }
    answer = max(answer,help(A));
    return answer;
    
}

Analysis

Compile error

In file included from user.cpp:20:0:
func.cpp:18:9: error: stray '\357' in program
         g[i] = max(g[i + 1ï¼½, 0) + a[i];
         ^
func.cpp:18:9: error: stray '\274' in program
func.cpp:18:9: error: stray '\275' in program
func.cpp: In function 'int help(std::vector<int>&)':
func.cpp:18:24: warning: left operand of comma operator has no effect [-Wunused-value]
         g[i] = max(g[i + 1ï¼½, 0) + a[i];
                        ^
func.cpp:18:33: error: expected ']' before ')' token
         g[i] = max(g[i + 1ï¼½, 0) + a[i];
                                 ^
func.cpp:18:33: error: no matching function for call to 'max(__gnu_cxx::__alloc_traits<std::allocator<int> >::value_type&)'
func.cpp:18:33: note: candidates are:
In file included from /usr/include/c++/4.8/bits/char_traits.h:39:0,
                 from /usr/include/c++/4.8/string:40,
                 from user.cpp:4:
/usr/include/c++/4.8/bits/stl_algobase.h:216:5: note: template<class _Tp> const _Tp& std::max(const _Tp&, const _Tp&)
     max(const _Tp& __a, const _Tp& __b)
     ^
/usr/include/c++/4.8/bits/stl_algobase.h:216:5: note:   template argument deduction/substitution failed:
In file included from user.cpp:20:0:
func.cpp:18:33: note:   candidate expects 2 arguments, 1 provided
         g[i] = max(g[i + 1ï¼½, 0) + a[i];
                                 ^
In file included from /usr/include/c++/4.8/bits/char_traits.h:39:0,
                 from /usr/include/c++/4.8/string:40,
                 from user.cpp:4:
/usr/include/c++/4.8/bits/stl_algobase.h:260:5: note: template<class _Tp, class _Compare> const _Tp& std::max(const _Tp&, const _Tp&, _Compare)
     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
     ^
/usr/include/c++/4.8/bits/stl_algobase.h:260:5: note:   template argument deduction/substitution failed:
In file included from user.cpp:20:0:
func.cpp:18:33: note:   candidate expects 3 arguments, 1 provided
         g[i] = max(g[i + 1ï¼½, 0) + a[i];
                                 ^
In file included from /usr/include/c++/4.8/algorithm:62:0,

Code: 13:53:38 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 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

// you can also use includes, for example:
#include <algorithm>

int help(vector<int> &a) {
    int n = a.size();
    vector<int> f,g;
    f.resize(n);
    f[0] = a[0];
    int now = a[0];
    for (int i = 1; i < n; ++i) {
        now = max(now, a[i]);
        f[i] = max(a[i] + f[i - 1], now);
    }
    g.resize(n);
    g[n - 1] = a[n - 1];
    int answer = a[n - 1];
    for (int i = n - 2; i >= 0; --i) {
        g[i] = max(g[i + 1], 0) + a[i];
        answer = max(answer, g[i]);
    }
    for (int i = 1; i < n; ++i) {
        answer = max(answer, g[i] - a[i] + f[i - 1]);
    }
    return answer;
}

int solution(vector<int> &A) {
    // write your code in C++11
    int answer = help(A);
    for (int i = 0, j = A.size() - 1; i < j; ++i,--j) {
        swap(A[i],A[j]);
    }
    answer = max(answer,help(A));
    return answer;
    
}

Analysis

▶

example
example test

✔

Code: 13:54:02 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 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

// you can also use includes, for example:
#include <algorithm>

int help(vector<int> &a) {
    int n = a.size();
    vector<int> f,g;
    f.resize(n);
    f[0] = a[0];
    int now = a[0];
    for (int i = 1; i < n; ++i) {
        now = max(now, a[i]);
        f[i] = max(a[i] + f[i - 1], now);
    }
    g.resize(n);
    g[n - 1] = a[n - 1];
    int answer = a[n - 1];
    for (int i = n - 2; i >= 0; --i) {
        g[i] = max(g[i + 1], 0) + a[i];
        answer = max(answer, g[i]);
    }
    for (int i = 1; i < n; ++i) {
        answer = max(answer, g[i] - a[i] + f[i - 1]);
    }
    return answer;
}

int solution(vector<int> &A) {
    // write your code in C++11
    int answer = help(A);
    for (int i = 0, j = A.size() - 1; i < j; ++i,--j) {
        swap(A[i],A[j]);
    }
    answer = max(answer,help(A));
    return answer;
    
}

Analysis

▶

example
example test

✔

Code: 13:54:07 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 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

// you can also use includes, for example:
#include <algorithm>

int help(vector<int> &a) {
    int n = a.size();
    vector<int> f,g;
    f.resize(n);
    f[0] = a[0];
    int now = a[0];
    for (int i = 1; i < n; ++i) {
        now = max(now, a[i]);
        f[i] = max(a[i] + f[i - 1], now);
    }
    g.resize(n);
    g[n - 1] = a[n - 1];
    int answer = a[n - 1];
    for (int i = n - 2; i >= 0; --i) {
        g[i] = max(g[i + 1], 0) + a[i];
        answer = max(answer, g[i]);
    }
    for (int i = 1; i < n; ++i) {
        answer = max(answer, g[i] - a[i] + f[i - 1]);
    }
    return answer;
}

int solution(vector<int> &A) {
    // write your code in C++11
    int answer = help(A);
    for (int i = 0, j = A.size() - 1; i < j; ++i,--j) {
        swap(A[i],A[j]);
    }
    answer = max(answer,help(A));
    return answer;
    
}

Analysis summary

The solution obtained perfect score.

Analysis

Detected time complexity:

O(N)

▶

example
example test

✔

▶

the_same_values
all the same values

✔

▶

double
two elements

✔

▶

simple1
simple tests, only few elements

✔

▶

simple2
simple tests, only few elements

✔

▶

small_random
small random sequences length = ~50

✔

▶

medium_cyclic
medium cyclic test, length = ~300

✔

▶

medium_random
medium random sequences length = ~5,000

✔

▶

large_random
large random sequences length = ~100,000

✔

▶

large_random_chunks
large random sequences length = ~100,000

✔

▶

large_extreme
all maximal/minimal values

✔