// codesnip-guard: maximum_scoring_segment_sets
#[cfg_attr(any(),rustfmt::skip)]pub use self::maximum_scoring_segment_sets::maximum_scoring_segment_sets;#[cfg_attr(any(),rustfmt::skip)]mod maximum_scoring_segment_sets{use super::{DoublyLinkedList,Zero};use std::{cmp::{Ordering,Reverse},ops::{Add,Neg}};#[doc=" Returns the maximum total score of exactly `k` nonempty disjoint segments for each `k`."]pub fn maximum_scoring_segment_sets<T>(scores:&[T])->Vec<T>where T:Clone+Ord+Zero+Add<Output=T>+Neg<Output=T>{let n=scores.len();let zero=T::zero();let mut positive_sum=zero.clone();let mut nonnegative_count=0;let mut negative_scores=Vec::with_capacity(n);let mut blocks:Vec<T>=Vec::with_capacity(n);for score in scores{let ordering=score.cmp(&zero);match ordering{Ordering::Greater=>{positive_sum=positive_sum+score.clone();nonnegative_count+=1;}Ordering::Equal=>{nonnegative_count+=1;continue;}Ordering::Less=>negative_scores.push(Reverse(score.clone())),}if let Some(last)=blocks.last_mut()&&((*last).cmp(&zero)==Ordering::Greater)==(ordering==Ordering::Greater){*last=last.clone()+score.clone();}else{blocks.push(score.clone());}}if blocks.first().is_some_and(|score|score<&zero){blocks.remove(0);}if blocks.last().is_some_and(|score|score<&zero){blocks.pop();}let mut result=vec![zero.clone();n+1];let segment_count=blocks.len().div_ceil(2);for value in&mut result[segment_count..=nonnegative_count]{value.clone_from(&positive_sum);}negative_scores.sort_unstable();let mut score_with_negatives=positive_sum.clone();for(offset,Reverse(score))in negative_scores.into_iter().enumerate(){score_with_negatives=score_with_negatives+score;result[nonnegative_count+offset+1].clone_from(&score_with_negatives);}if segment_count<=1{return result;}let block_count=blocks.len();let mut links=DoublyLinkedList::new(block_count);for index in 1..block_count{links.link(index-1,index);}let absolute=|value:&T|{if value<&zero{-value.clone()}else{value.clone()}};let mut weights:Vec<_>=blocks.iter().map(|block|Some(absolute(block))).collect();let mut candidates:Vec<_>=(0..block_count).collect();let mut losses=Vec::with_capacity(segment_count);for _ in 1..segment_count{let(index,left,right)=loop{let index=candidates.pop().expect("a live block sequence must have a local minimum");if weights[index].is_none(){continue;}let left=links.prev(index);let right=links.next(index);if(left==usize::MAX||weights[index]<=weights[left])&&(right==usize::MAX||weights[index]<=weights[right]){break(index,left,right);}};losses.push(weights[index].take().expect("a local minimum must be live"));if left==usize::MAX{links.detach(index);let(_,next)=links.detach(right);weights[right]=None;candidates.push(next);}else if right==usize::MAX{let(prev,_)=links.detach(left);links.detach(index);weights[left]=None;candidates.push(prev);}else{blocks[index]=blocks[left].clone()+blocks[index].clone()+blocks[right].clone();weights[index]=Some(absolute(&blocks[index]));let(prev,_)=links.detach(left);let(_,next)=links.detach(right);weights[left]=None;weights[right]=None;candidates.extend([prev,index,next].into_iter().filter(|&index|index!=usize::MAX));}}losses.extend(weights.into_iter().flatten());losses.sort_unstable();let mut current_score=positive_sum;for(result,loss)in result[..segment_count].iter_mut().rev().zip(losses){current_score=current_score+-loss;result.clone_from(&current_score);}result}}
// codesnip-guard: DoublyLinkedList
#[cfg_attr(any(),rustfmt::skip)]pub use self::doubly_linked_list::DoublyLinkedList;#[cfg_attr(any(),rustfmt::skip)]mod doubly_linked_list{#[doc=" Manages only prev/next links of indices."]#[doc=""]#[doc=" `usize::MAX` means no previous or next index."]#[derive(Debug,Clone)]pub struct DoublyLinkedList{prev:Vec<usize>,next:Vec<usize>}impl DoublyLinkedList{pub fn new(n:usize)->Self{Self{prev:vec![usize::MAX;n],next:vec![usize::MAX;n]}}pub fn len(&self)->usize{self.prev.len()}pub fn is_empty(&self)->bool{self.len()==0}pub fn prev(&self,index:usize)->usize{self.prev[index]}pub fn next(&self,index:usize)->usize{self.next[index]}#[doc=" Links `front` immediately before `back`."]#[doc=""]#[doc=" Panics if `front == back`, `front` already has a next index, or `back` already has a"]#[doc=" previous index."]pub fn link(&mut self,front:usize,back:usize){assert_ne!(front,back);assert_eq!(self.next[front],usize::MAX);assert_eq!(self.prev[back],usize::MAX);self.next[front]=back;self.prev[back]=front;}pub fn cut_before(&mut self,index:usize)->usize{let prev=self.prev[index];if prev!=usize::MAX{self.next[prev]=usize::MAX;self.prev[index]=usize::MAX;}prev}pub fn cut_after(&mut self,index:usize)->usize{let next=self.next[index];if next!=usize::MAX{self.prev[next]=usize::MAX;self.next[index]=usize::MAX;}next}#[doc=" Panics when removing an index from a two-node cycle."]pub fn detach(&mut self,index:usize)->(usize,usize){let prev=self.cut_before(index);let next=self.cut_after(index);if prev!=usize::MAX&&next!=usize::MAX{self.link(prev,next);}(prev,next)}}}
// codesnip-guard: zero_one
#[cfg_attr(any(),rustfmt::skip)]pub use self::zero_one::{One,Zero};#[cfg_attr(any(),rustfmt::skip)]mod zero_one{pub trait Zero:Sized{fn zero()->Self;#[inline]fn is_zero(&self)->bool where Self:PartialEq{self==&Self::zero()}#[inline]fn set_zero(&mut self){*self=Self::zero();}}pub trait One:Sized{fn one()->Self;#[inline]fn is_one(&self)->bool where Self:PartialEq{self==&Self::one()}#[inline]fn set_one(&mut self){*self=Self::one();}}macro_rules!impl_zero_one{($({$(<$T:ident:$Bound:ident>)?$Trait:ident$method:ident$($t:ty)*,$e:expr})*)=>{$(impl_zero_one!(@impl[$(<$T:$Bound>)?]$Trait$method[$($t)*],$e);)*};(@impl[<$T:ident:$Bound:ident>]$Trait:ident$method:ident[$($t:ty)*],$e:expr)=>{$(impl<$T:$Bound>$Trait for$t{fn$method()->Self{$e}})*};(@impl[]$Trait:ident$method:ident[$($t:ty)*],$e:expr)=>{$(impl$Trait for$t{fn$method()->Self{$e}})*};}impl_zero_one!({Zero zero u8 u16 u32 u64 usize i8 i16 i32 i64 isize u128 i128,0}{Zero zero f32 f64,0.}{One one u8 u16 u32 u64 usize i8 i16 i32 i64 isize u128 i128,1}{One one f32 f64,1.}{<T:Zero>Zero zero std::num::Wrapping<T>,Self(T::zero())}{<T:One>One one std::num::Wrapping<T>,Self(T::one())});}