When it comes to O(N log(N)) time complexity functions, this is the right section.

Given an array of natural numbers (later, you will see, it can be real, or any other less complex system (rational, irrational)) and you create a tree of all permutations preserving conjugation order.

array = c(1,2,3,4)
#sub-array with sum in [] brackets
1. c(1) [1]
2. c(1,2)     [3]
3. c(1,2,3)  [6]
4. c(1,2,3,4) [10]
6. c(2) [2]
7. c(2,3) [5]
8. c(2,3,4) [9]
10. c(3) [3]
11. c(3,4) [7]
13. c(4) [4]

with total SUM = 1+3+6+10+2+5+9+3+7+4 = 50

With simple R function, we can achieve this by:

arr = c(1,2,3,4,4,5,6,7,7,6,5,4,3,1)

sumArr <- function(x){
  summ <- 0
  i <- 1
  for (i in 1:length(arr)) {
    j <- i + 0
    midsum <- 0
    for (j in j:length(arr)) {
      midsum <- sum(arr[i:j])
      summ <- summ + midsum
      #print(sum)
    }
  }
  cat(paste0("Total sum of sub-arrays: ", summ))
 }

#calling function
sumArr(arr)

Ok, this was useless and straightforward. What if we decide to find the maximums of each array and create a total sum:

array = c(1,2,3,4)
#sub-array with sum in [] brackets
1. c(1) [1]
2. c(1,2)     [2]
3. c(1,2,3)  [3]
4. c(1,2,3,4) [4]
6. c(2) [2]
7. c(2,3) [3]
8. c(2,3,4) [4]
10. c(3) [3]
11. c(3,4) [4]
13. c(4) [4]

with total SUM = 1+2+3+4+2+3+4+3+4+4 = 30


sumArrOfMax <- function(x){
  summ <- 0
  i <- 1
  for (i in 1:length(arr)) {
    j <- i + 0
    midsum <- 0
    for (j in j:length(arr)) {
      midsum <- max(arr[i:j])
      summ <- summ + midsum
      #print(sum)
    }
  }
  cat(paste0("Total sum of maximums of all sub-arrays: ", summ))
}

# run function
sumArrOfMax(arr)

As always, code is available on the Github in the same Useless_R_function repository. Check Github for future updates.

Happy R-coding and stay healthy!“