Ein Codility-Test, der gelöst werden muss

Question

Ich kann die Frage nicht verstehen, kann jemand es ein wenig klären?

Update: hier ist meine Lösung Kadane Algorithmus aber es funktioniert nicht in der folgenden 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; 

Answer 1

Die Funktion kann aussehen, wie es

im demonstrativen Programm gezeigt wird

#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; 
} 

Sein Ausgang ist

Sie können die Funktion mithilfe von Indizes anstelle von Iteratoren neu schreiben.

Was Ihre Funktion ist es zumindest in Bezug auf diese Bedingung

if (max_ending_here < 0) 
     max_ending_here = 0; 

falsch, da stattdessen das aktuelle Element zu prüfen, ob es kleiner als Null ist die Bedingung ist die aktuelle Summe der Elemente überprüft.