Kanade 알고리즘(C++17 기반) - Maximum Sum Subarray Problem(최대 합을 갖는 부분 배열 찾기?)

0. 이건 뭔고?

연속된 시간 상의 영상 간의 optical flow를 추정하는데 유용하다고 하며, stereo imaging에서 depth map을 산출 할때 신뢰할 수 있는 기준점(ground control points)을 확보하는데 유용하다고 한다. 우선 이렇게 알아 두고 차츰 어떻게 적용되는지 알아 보도록 하자.

1. 내부변수

possible_subsum : 최대 부분합이 될 가능성이 있는 부분합

restart : possible_subsum 이 갱신되는 시점의 시작지점

max_subsum : 최대 부분합으로 possible_subsum과 항시 비교하여 최대값으로 유지된다.

start : max_subsum이 갱신되는 시점의 restart의 저장 변수

finish : max_subsum이 갱신되는 시점의 내부항목의 현재 위치

2. 사용법

    vector<int> a = { -8, -3, -6, -2, -5, -4 };

    auto [subsum, i, j] = kanade(a);

3. 코드

4. 컴파일 

$ g++ -std=c++17 kanada.cc -o kanada

$ ./kanada