[C++ 풀이] Codility - Lessons 9 (Maximum slice problem), MaxSliceSum

이 문제는 Codility 사이트에서 확인하고 문제를 풀 수 있습니다.

https://www.codility.com/

 

 

 

 

 

문제

 

 

 

 

설명

 

비어있지 않은 배열 A가 주어집니다.

 

배열 A의 길이는 1 ~ 1,000,000 이며, A[N]의 요소들은 -1,000,000 ~ 1,000,000이 될 수 있습니다.

 

그리고 배열들 요소의 최종 합은 int의 범위인 -2,147,483,648 ~ 2,147,483,647 입니다.

 

이때 배열 요소들의 합 중 가장 큰 합을 구하는 문제입니다.

 

 

 

 

 

결과

 

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

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

int solution(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    if(A.size() < 2)
        return A[0];
    
    vector<int> max;
    
    max.push_back(A[0]);
    
    for(int i = 1; i < A.size(); i++)
        max.push_back((max[i - 1] + A[i] > A[i]) ? max[i - 1] + A[i] : A[i]);


    int result = max[0];

    for(int i = 1; i < max.size(); i++)
        result = (result < max[i]) ? max[i] : result;
        
    return result;
}​

 

 

 

https://app.codility.com/demo/results/training8USD6F-2NU/

 

 

 

이 문제는 상당히 어려운 문제입니다.

 

왜냐하면 배열 요소중 음수가 있기 때문입니다.

 

따라서 범위마다 최대 값을 계산해서 값을 추론해야 하는데, 문제에서 원하는 속도는 O(n) 입니다.

 

for문 하나만 돌려서 결과를 추론해야 합니다.

 

저도 이 문제는 보자마자 '턱!!...'하고 막혀서 인터넷을 찾아서 풀었습니다.

 

풀이 방법은 간단한데 Kadane's algorithm(클릭) 으로 풀면 됩니다.

 

이것에 대한 설명은 길어진 따로 빼서 설명하겠고, 위 코드만 간략하게 설명하겠습니다.

 

각 범위별로 합의 최대 값을 max 백터에 넣어두고 for문이 끝나면 max 백터에 있는 요소들 중 가장 큰 값을 찾아내는 코드 입니다.