use crate::Vec1;
impl<T> Vec1<T>
where
T: Copy + core::ops::Add<Output = T> + PartialOrd + Default,
{
pub fn max_subarray_sum(&self) -> (T, usize, usize) {
if self.is_empty() {
return (T::default(), 0, 0);
}
let mut best = self[1];
let mut cur = self[1];
let mut cur_start = 1;
let mut best_start = 1;
let mut best_end = 1;
for i in 2..=self.len() {
if cur < T::default() {
cur = self[i];
cur_start = i;
} else {
cur = cur + self[i];
}
if cur > best {
best = cur;
best_start = cur_start;
best_end = i;
}
}
(best, best_start, best_end)
}
pub fn max_subarray_product(&self) -> (T, usize, usize)
where
T: core::ops::Mul<Output = T>,
{
if self.is_empty() {
return (T::default(), 0, 0);
}
let mut max_p = self[1];
let mut min_p = self[1];
let mut max_start = 1;
let mut min_start = 1;
let mut best = self[1];
let mut best_start = 1;
let mut best_end = 1;
for i in 2..=self.len() {
let v = self[i];
let c1 = v;
let c2 = max_p * v;
let c3 = min_p * v;
let (new_max, new_max_start) = {
let mut val = c1;
let mut start = i;
if c2 >= val {
val = c2;
start = max_start;
}
if c3 >= val {
val = c3;
start = min_start;
}
(val, start)
};
let (new_min, new_min_start) = {
let mut val = c1;
let mut start = i;
if c2 <= val {
val = c2;
start = max_start;
}
if c3 <= val {
val = c3;
start = min_start;
}
(val, start)
};
max_p = new_max;
max_start = new_max_start;
min_p = new_min;
min_start = new_min_start;
if max_p > best {
best = max_p;
best_start = max_start;
best_end = i;
}
}
(best, best_start, best_end)
}
}
impl<T> Vec1<T>
where
T: Copy + PartialEq,
{
pub fn majority_element(&self) -> Option<T> {
if self.is_empty() {
return None;
}
let mut cand = self[1];
let mut count = 0i64;
for &x in self.iter() {
if count == 0 {
cand = x;
count = 1;
} else if x == cand {
count += 1;
} else {
count -= 1;
}
}
let cnt = self.iter().filter(|&&x| x == cand).count();
if cnt > self.len() / 2 { Some(cand) } else { None }
}
pub fn majority_elements_n3(&self) -> Vec1<T> {
if self.is_empty() {
return Vec1::new();
}
let mut c1: Option<T> = None;
let mut c2: Option<T> = None;
let mut n1 = 0usize;
let mut n2 = 0usize;
for &x in self.iter() {
if Some(x) == c1 {
n1 += 1;
} else if Some(x) == c2 {
n2 += 1;
} else if n1 == 0 {
c1 = Some(x);
n1 = 1;
} else if n2 == 0 {
c2 = Some(x);
n2 = 1;
} else {
n1 -= 1;
n2 -= 1;
}
}
let mut result = Vec1::new();
let thr = self.len() / 3;
if let Some(c) = c1 {
if self.iter().filter(|&&x| x == c).count() > thr {
result.push(c);
}
}
if let Some(c) = c2 {
if c1 != Some(c) && self.iter().filter(|&&x| x == c).count() > thr {
result.push(c);
}
}
result
}
}
impl<T> Vec1<T>
where
T: Copy,
{
pub fn reservoir_sample(&self, k: usize) -> Vec1<T> {
if k == 0 || self.is_empty() {
return Vec1::new();
}
let k = k.min(self.len());
let mut res = Vec1::with_capacity(k);
for i in 1..=k {
res.push(self[i]);
}
let mut state: u64 = 0x9E37_79B9_7F4A_7C15;
let mut next = |max: u64| -> u64 {
state = state.wrapping_mul(6364136223846793005).wrapping_add(1442695040888963407);
(state >> 33) % max
};
for i in (k + 1)..=self.len() {
let j = next(i as u64) as usize + 1;
if j <= k {
res[j] = self[i];
}
}
res
}
}
#[cfg(test)]
mod tests {
use crate::{Vec1, vec1};
#[test]
fn max_subarray_sum_basic() {
let v = vec1![-2, 1, -3, 4, -1, 2, 1, -5, 4];
let (s, a, b) = v.max_subarray_sum();
assert_eq!(s, 6);
assert_eq!(a, 4);
assert_eq!(b, 7);
}
#[test]
fn max_subarray_sum_single_negative() {
let v = vec1![-5];
let (s, a, b) = v.max_subarray_sum();
assert_eq!(s, -5);
assert_eq!(a, 1);
assert_eq!(b, 1);
}
#[test]
fn max_subarray_product_basic() {
let v: Vec1<i32> = vec1![2, -5, -2, 4, -1];
let (p, a, b) = v.max_subarray_product();
assert_eq!(p, 80);
assert_eq!(a, 1);
assert_eq!(b, 4);
}
#[test]
fn max_subarray_product_simple() {
let v: Vec1<i32> = vec1![1, 2, 3, 4];
let (p, a, b) = v.max_subarray_product();
assert_eq!(p, 24);
assert_eq!(a, 1);
assert_eq!(b, 4);
}
#[test]
fn max_subarray_product_with_zero() {
let v: Vec1<i32> = vec1![-2, 0, -3];
let (p, a, b) = v.max_subarray_product();
assert_eq!(p, 0);
assert_eq!(a, 1);
assert_eq!(b, 2);
}
#[test]
fn max_subarray_product_single() {
let v: Vec1<i32> = vec1![5];
let (p, a, b) = v.max_subarray_product();
assert_eq!(p, 5);
assert_eq!(a, 1);
assert_eq!(b, 1);
}
#[test]
fn max_subarray_product_all_negative() {
let v: Vec1<i32> = vec1![-1, -2, -3];
let (p, _a, _b) = v.max_subarray_product();
assert_eq!(p, 6);
}
#[test]
fn majority_element_basic() {
let v = vec1![1, 2, 1, 1, 3, 1, 1];
assert_eq!(v.majority_element(), Some(1));
}
#[test]
fn majority_element_none() {
let v = vec1![1, 2, 3, 4];
assert_eq!(v.majority_element(), None);
}
#[test]
fn majority_elements_n3_basic() {
let v = vec1![1, 2, 1, 3, 1, 2, 2];
let mut r = v.majority_elements_n3();
r.as_mut_slice().sort();
assert_eq!(r.as_slice(), &[1, 2]);
}
#[test]
fn majority_elements_n3_none() {
let v = vec1![1, 2, 3];
assert!(v.majority_elements_n3().is_empty());
}
#[test]
fn reservoir_sample_len() {
let v = vec1![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
assert_eq!(v.reservoir_sample(3).len(), 3);
}
#[test]
fn reservoir_sample_k_larger_than_len() {
let v = vec1![1, 2, 3];
assert_eq!(v.reservoir_sample(10).len(), 3);
}
#[test]
fn reservoir_sample_zero() {
let v = vec1![1, 2, 3];
assert!(v.reservoir_sample(0).is_empty());
}
}