Kanade 알고리즘(C++17 기반)

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