misc-problem-solutions/include/forfun/maximum_subarray.hpp at main · oboukli/misc-problem-solutions · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
// Copyright (c) Omar Boukli-Hacene. All rights reserved.
// Distributed under an MIT-style license that can be
// found in the LICENSE file.

// SPDX-License-Identifier: MIT

/// Problem sources:
/// https://en.wikipedia.org/wiki/Maximum_subarray_problem

#ifndef FORFUN_MAXIMUM_SUBARRAY_HPP_
#define FORFUN_MAXIMUM_SUBARRAY_HPP_

#include <algorithm>
#include <concepts>
#include <iterator>
#include <limits>
#include <utility>

namespace forfun::maximum_subarray {

template <typename T>
    requires std::integral<T>
using PromotedValueType = decltype(std::declval<T>() + std::declval<T>());

namespace brute_force {

template <typename Iter, typename Sentinel>
    requires std::forward_iterator<Iter>
    and std::sentinel_for<Iter, Sentinel>
    and std::integral<std::iter_value_t<Iter>>
[[nodiscard]] constexpr auto
max_sum(Iter const first, Sentinel const last) noexcept
    -> PromotedValueType<std::iter_value_t<Iter>>
{
    using std::numeric_limits;

    using T = PromotedValueType<std::iter_value_t<Iter>>;

    if (first == last) [[unlikely]]
    {
        return T{};
    }

    T max_sum{numeric_limits<T>::min()};
    for (auto iter_i{first}; iter_i != last; ++iter_i)
    {
        T sum{};
        for (auto iter_j{iter_i}; iter_j != last; ++iter_j)
        {
            sum += *iter_j;
            if (sum > max_sum)
            {
                max_sum = sum;
            }
        }
    }

    return max_sum;
}

} // namespace brute_force

namespace recursive {

namespace detail {

template <typename Iter, typename Sentinel>
    requires std::input_iterator<Iter>
    and std::sentinel_for<Iter, Sentinel>
    and std::integral<std::iter_value_t<Iter>>
[[nodiscard]] constexpr auto max_sum_internal(
    Iter iter,
    Sentinel const last,
    PromotedValueType<std::iter_value_t<Iter>> sum
) noexcept -> PromotedValueType<std::iter_value_t<Iter>>
{
    using std::max;

    if (iter == last) [[unlikely]]
    {
        return sum;
    }

    PromotedValueType<std::iter_value_t<Iter>> const num{*iter};
    sum = max(num, num + sum);

    return max(sum, max_sum_internal(++iter, last, sum));
}

} // namespace detail

template <typename Iter, typename Sentinel>
    requires std::input_iterator<Iter>
    and std::sentinel_for<Iter, Sentinel>
    and std::integral<std::iter_value_t<Iter>>
[[nodiscard]] constexpr auto max_sum(Iter iter, Sentinel const last) noexcept
    -> PromotedValueType<std::iter_value_t<Iter>>
{
    using std::min;

    using T = PromotedValueType<std::iter_value_t<Iter>>;

    if (iter == last) [[unlikely]]
    {
        return T{};
    }

    return detail::max_sum_internal(iter, last, min(T{}, *iter));
}

} // namespace recursive

namespace streaming {

template <typename Iter, typename Sentinel>
    requires std::input_iterator<Iter>
    and std::sentinel_for<Iter, Sentinel>
    and std::integral<std::iter_value_t<Iter>>
[[nodiscard]] constexpr auto max_sum(Iter iter, Sentinel const last) noexcept
    -> PromotedValueType<std::iter_value_t<Iter>>
{
    using std::max;
    using std::min;

    using T = PromotedValueType<std::iter_value_t<Iter>>;

    if (iter == last) [[unlikely]]
    {
        return T{};
    }

    T sum{min(T{}, *iter)};
    T max_sum{sum};
    for (; iter != last; ++iter)
    {
        T const num{*iter};
        sum = max(num, num + sum);

        if (sum > max_sum)
        {
            max_sum = sum;
        }
    }

    return max_sum;
}

} // namespace streaming

} // namespace forfun::maximum_subarray

#endif // FORFUN_MAXIMUM_SUBARRAY_HPP_