How to find larger increasing or decreasing subsequence in a vector?

Question

I have the following vector:

a <- c(1,2,3,1,1,2,3,4,2,5,6,7,8,4,6,4,3,2,1)

I would like to find the largest increasing and decreasing subsequence of it. The output would be the indices of the sequence of vectors:

ss_cres <- c(9,10,11,12,13) # ou seja 2,5,6,7 e 8

ss_decres <- c(15,16,17,18,19) # ou seja 6,4,3,2 e 1

This is a common operation used in time series analysis. Is there a package in R that does this? If not, any hint for a general idea for the experiment-based algorithm?

So far I have done this for the largest decreasing series:

long_seq_decres<- function(seq){

seq_inds <- split(1:length(seq), cumsum(c(0, diff(seq)) > 0))  
  
ind_list <- lengths(seq_inds)

long_seq_inds <- seq_inds[which.max(ind_list)]

return(long_seq_inds)

}

It worked well, however I found it a little slow function. Any idea to optimize this function?

Answer 1

Can use rle to save the step of creating the split list:

long_seq_dec <- function(seq) {
  seq_inds <- split(1:length(seq), cumsum(c(0, diff(seq)) > 0))
  ind_list <- lengths(seq_inds)
  seq_inds[[which.max(ind_list)]]
}

long_seq <- function(seq, type = c("increasing", "decreasing")) {
  type <- match.arg(type)
  dif <- c(0, diff(seq))
  csd <- if (type == "increasing") cumsum(dif <= 0) else cumsum(dif > 0)
  cmps <- rle(csd)
  seq_len(length(seq))[csd == with(cmps, values[lengths == max(lengths)])]
}

a <- c(1,2,3,1,1,2,3,4,2,5,6,7,8,4,6,4,3,2,1)

long_seq_dec(a)
#> [1] 15 16 17 18 19

long_seq(a, "d")
#> [1] 15 16 17 18 19

long_seq(a)
#> [1]  9 10 11 12 13


library(microbenchmark)

x <- sample(1:10, 1e4, TRUE)

microbenchmark(long_seq_dec(x), long_seq(x, "d"))
#> Unit: milliseconds
#>             expr      min       lq     mean   median       uq       max neval
#>  long_seq_dec(x) 5.701912 5.916570 6.247751 5.976668 6.200649 13.209920   100
#> long_seq(x, "d") 1.627581 1.684397 1.919555 1.718479 1.869197  8.719684   100