[Codility] Max Slice Sum

링크 : https://app.codility.com/programmers/lessons/9-maximum_slice_problem/max_slice_sum/

Max Slice 알고리즘 설명 : https://haewoneee.tistory.com/161

 

기존 max slice 알고리즘에서 약간 변형해서 풀어야 한다.

모든 slice 의 합이 음수여도 0이 아닌 음수를 반환하도록 변형해야 한다.

int solution(vector<int>& arr) 
{
    int maxEnding = 0;
    int maxSlice = arr[0];

    for (int index = 0; index < arr.size(); ++index)
    {
        int currentNum = arr[index];
        maxSlice = max(maxSlice, maxEnding + currentNum);
        maxEnding = max( 0, maxEnding + currentNum);
    }

    return maxSlice;
}