pub(super) fn is_concave<T>(values: &[T]) -> boolwhere
T: Signed,Examples found in repository?
crates/competitive/src/math/min_plus_convolution/concave.rs (line 169)
161pub fn min_plus_convolution_concave_envelope<T>(a: &[T], b: &[T]) -> Vec<T>
162where
163 T: Signed,
164{
165 let len = output_len(a.len(), b.len());
166 if len == 0 {
167 return Vec::new();
168 }
169 let a_is_concave = !a.iter().any(T::is_maximum) && is_concave(a);
170 let b_is_concave = !b.iter().any(T::is_maximum) && is_concave(b);
171 let (arbitrary, concave) = if b_is_concave {
172 (a, b)
173 } else if a_is_concave {
174 (b, a)
175 } else {
176 panic!("at least one min-plus convolution input must be finite and concave")
177 };
178 concave_envelope(arbitrary, concave)
179}
180
181pub(super) fn concave_envelope<T>(arbitrary: &[T], concave: &[T]) -> Vec<T>
182where
183 T: Signed,
184{
185 if concave.len() == 1 {
186 return arbitrary
187 .iter()
188 .map(|&value| {
189 if value.is_maximum() {
190 T::maximum()
191 } else {
192 value + concave[0]
193 }
194 })
195 .collect();
196 }
197 if arbitrary.len() == 1 {
198 return if arbitrary[0].is_maximum() {
199 vec![T::maximum(); concave.len()]
200 } else {
201 concave.iter().map(|&value| arbitrary[0] + value).collect()
202 };
203 }
204
205 ConcaveEnvelope::new(arbitrary, concave).convolve()
206}
207
208/// Computes convolution of two concave inputs from antidiagonal endpoints.
209///
210/// The running time is `O(n + m)`.
211///
212/// # Panics
213///
214/// Panics unless both inputs are finite and concave.
215pub fn min_plus_convolution_concave_both<T>(a: &[T], b: &[T]) -> Vec<T>
216where
217 T: Signed,
218{
219 let len = output_len(a.len(), b.len());
220 if len == 0 {
221 return Vec::new();
222 }
223 assert_finite(a);
224 assert_finite(b);
225 assert!(
226 is_concave(a) && is_concave(b),
227 "both inputs must be concave"
228 );
229 concave_both(a, b)
230}