andre - 1 year ago 129
C++ Question

A Codility test that needs to be solved

I can not understand the question, can someone clarify it a little bit ?

Update : here is my solution using Kadane algorithm but it fails at the following arrays:

``````Example test:    [-8, 3, 0, 5, -3, 12]
WRONG ANSWER  (got 17 expected 12)

Example test:    [-1, 2, 1, 2, 0, 2, 1, -3, 4, 3, 0, -1]
WRONG ANSWER  (got 12 expected 8)

int max_so_far = 0, max_ending_here = 0;

for (int i = 0; i < A.size(); i++)
{
max_ending_here = max_ending_here + A[i];
if (max_ending_here < 0)
max_ending_here = 0;
if (max_so_far < max_ending_here)
max_so_far = max_ending_here;
}
return max_so_far;
``````

The function can look as it is shown in the demonstrative program

``````#include <iostream>
#include <algorithm>
#include <vector>

long long int solution( const std::vector<int> &v )
{
long long int max_sum = 0;

for ( auto it = v.begin();
( it = std::find_if( it, v.end(), []( int x ) { return !( x < 0 ); } ) ) != v.end();
)
{
long long int sum = 0;

while ( it != v.end() && !( *it < 0 ) ) sum += *it++;

if ( max_sum < sum ) max_sum = sum;
}

return max_sum;
}

int main()
{
std::vector<int> v = { 1, 2, -3, 4, 5, -6 };

std::cout << solution( v ) << std::endl;

return 0;
}
``````

Its output is

``````9
``````

You can rewrite the function using indices instead of iterators.

As for your function then it is incorrect at least relative to this condition

``````    if (max_ending_here < 0)
max_ending_here = 0;
``````

because instead of checking the current element whether it is less than zero the condition checks the current sum of elements.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download