Rosetta Code

Longest increasing subsequence: Difference between revisions

Page Discussion

Longest increasing subsequence (view source)

Revision as of 19:00, 4 September 2021

152 bytes removed ,  2 years ago
→‎{{header|Rust}}: I've reverted the Rust code back to the original submission by Donkey-hotei (though it now takes a slice arg rather than a Vec). The version which had been current gave the wrong answers!
(→‎{{header|Rust}}: I've reverted the Rust code back to the original submission by Donkey-hotei (though it now takes a slice arg rather than a Vec). The version which had been current gave the wrong answers!)
Line 2,316:
=={{header|Rust}}==
 
<lang Rust>
<lang Rust>fn lower_bound<T: PartialOrd>(list: &Vec<T>, value: &T) -> usize {
fn lis(x: &[i32])-> Vec<i32> {
if list.is_empty() {
let n = return 0x.len();
let mut m = vec![0; n];
}▼
let mut lowerp = 0usizevec![0; n];
let mut upperl = list.len()0;
 
while lower != upper {
for i in list[10..].iter()n {▼
let middle = lower + upper >> 1;▼
iflet list[middle]mut <lo *value= {1;
let mut lowerhi = middle + 1l;
 
} else {▼
while lo <= hi upper = middle;{
▲ let middlemid = lower(lo + upperhi) >>/ 12;
 
subseqif x[indexm[mid]] <= *x[i;] {▼
subseq.push(*i) lo = mid + 1;▼
▲ } else {
hi = mid - 1;
} else { }▼
}
}▼
return lower;
}
 
let new_l = lo;
fn lis<T: PartialOrd + Copy>(list: &Vec<T>) -> Vec<T> {
p[i] = m[new_l - 1];
if list.is_empty() {
returnm[new_l] Vec::new()= i;
 
}
let mut subseq: Vec<T if new_l > =l Vec::new();{
l = new_l;
subseq.push(*list.first().unwrap());
▲ for i in list[1..].iter() {
if *i <= *subseq.last().unwrap() {
let index = lower_bound(&subseq, i);
▲ subseq[index] = *i;
▲ } else {
▲ subseq.push(*i);
}
}
 
return subseq;
let mut o = vec![0; l];
let mut k = m[l];
for i in (0..l).rev() {
o[i] = x[k];
k = p[k];
▲ }
 
▲ }o
}
 
Line 2,358 ⟶ 2,364:
 
{{out}}
<pre>[12, 4, 5]
[0, 12, 36, 79, 11, 15]</pre>
 
=={{header|Scala}}==
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/234594"