test/kadane.test.cpp

View this file on GitHub
Last update: 2022-07-30 02:10:28+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A

Depends on

Kadane's Algorithm (最大連続部分和) (src/algorithm/Kadane.hpp)

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

#include "../src/algorithm/Kadane.hpp"
#include <iostream>
#include <cassert>

int main() {
    std::vector<int> ins = {-5, -1, 6, 4, 9, -6, -6, -7};
    zawa::Kadane<int> kadane(ins, -100);
    kadane.build();
    
    int ans = 19;
    int left = 2, right = 5;
    assert(left == kadane.get_seg().first);
    assert(right == kadane.get_seg().second);
    assert(ans == kadane.get());

    std::cout << "Hello World" << std::endl;
}

#line 1 "test/kadane.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

#line 2 "src/algorithm/Kadane.hpp"

#include <vector>

namespace zawa {

    template <typename T>
    class Kadane {

    private:
        std::vector<T> arr;
        std::pair<int, int> segment;
        T res;

    public:
        Kadane(std::vector<T>& arr, T init) 
            : arr(arr.begin(), arr.end()), 
              res(init) {}

        void build() {
            T dp = res;
            int left = 0;
            for (int right = 0 ; right < (int)arr.size() ; right++) {
                if (dp + arr[right] < arr[right]) {
                    left = right;
                }
                dp = std::max(dp + arr[right], arr[right]);

                if (res < dp) {
                    segment = {left, right};
                }
                res = std::max(res, dp);
            }
            segment.second++;
        }

        T get() {
            return res;
        }

        std::pair<int, int> get_seg() {
            return segment;
        }
    };

}// namespace zawa
#line 4 "test/kadane.test.cpp"
#include <iostream>
#include <cassert>

int main() {
    std::vector<int> ins = {-5, -1, 6, 4, 9, -6, -6, -7};
    zawa::Kadane<int> kadane(ins, -100);
    kadane.build();
    
    int ans = 19;
    int left = 2, right = 5;
    assert(left == kadane.get_seg().first);
    assert(right == kadane.get_seg().second);
    assert(ans == kadane.get());

    std::cout << "Hello World" << std::endl;
}