Find the minimal sum of the local maximum of the subarrays of an array-CodePudding

I need to write a function to calculate minimal sum of the local maximum of the subarrays of an array where every item is a positive integer with possible duplicates.

For example, we have an array [2, 3, 1, 4, 5, 6] and the number of sub arrays is 3. We want to get the min sum of the local max of the sub arrays. What that means is that, for example, one possible way to divide the current array into 3 sub arrays is [[2,3], [1], [4,5,6]] and the local maxs for each subarray is 3, 1, 6 respectively. And the sum of the local maxs is 3 1 6 = 10. For this particular array, [2, 3, 1, 4, 5, 6], this is the minimal sum of all its possible sub-array variations.

My approach is to first get all the possible sub-array variations for a given array. and get the min sum of them.


function getSubarrays(array, numOfSubarray) {
  const results = []

  const recurse = (index, subArrays) => {
    if (index === array.length && subArrays.length === numOfSubarray) {
      results.push([...subArrays])
      return
    }
    if (index === array.length) return

    // 1. push current item to the current subarray
    // when the remaining items are more than the remaining sub arrays needed

    if (array.length - index - 1 >= numOfSubarray - subArrays.length) {
      recurse(
        index   1,
        subArrays.slice(0, -1).concat([subArrays.at(-1).concat(array[index])])
      )
    }
    // 2. start a new subarray when the current subarray is not empty

    if (subArrays.at(-1).length !== 0)
      recurse(index   1, subArrays.concat([[array[index]]]))
  }

  recurse(0, [[]], 0)
  return results
}

function getMinSum(arrays) {
  return arrays.reduce(
    (minSum, array) =>
      Math.min(
        minSum,
        array.reduce((sum, subarray) => sum   Math.max(...subarray), 0)
      ),
    Infinity
  )
}
 
getMinSum(getSubarrays([[2,3], [1], [4,5,6]], 3)) // 10

However, I think the time complexity for my solution is really high. My guess is that it is on the order of 2^n (feel free to correct me if I am wrong). I wonder if there is a more efficient way to calculate this.

CodePudding user response：

The first thing that comes to mind is dynamic programming.

Let dp[i][j] be the minimal sum of local maximums of array[0..i] (left border included, right border excluded) divided into j subarrays. dp[0][0] = 0 (this is an initial value for empty array[0..0]), and for simplicity initialise all other dp[i][j] with some large enough number to denote meaningless of not calculated values (larger than sum of elements in array in this case is enough).

Your answer obviously is the value of dp[array.length][numOfSubarray].

How do you calculate values of the dp? Actually pretty easy. dp[i][j] is the minimum among dp[k][j - 1] max(array[k..i]) (where k < i). Let's analyse this formula:

dp[k][j - 1]   max(array[k..i])
#    ^                ^
# This term is the minimal sum of local maximums
# of array[0..k] divided into j-1 subarrays.
#                     |
#           This term is maximum of your new j-th subarray.

Also make sure that all the dp[k][j - 1] were calculated beforehand (for example by calculating dp[i][1] at first, then dp[i][2], then dp[i][3] and so on).

Now let's write it altogether (naive approach just for now).

dp[0][0] = 0

for newSubarrayNumber in range(1, numOfSubarray   1):
  for previousEnd in range(0, array.length):
     for newEnd in range(previousEnd   1, array.length   1):
       # Formula from above.
       dp[newEnd][newSubarrayNumber] = 
           min(dp[newEnd][newSubarrayNumber],
               dp[previousEnd][newSubarrayNumber - 1]   max(array[previousEnd..newEnd]))

 # Your answer.
print(dp[array.length][numOfSubarray])

As you can see we've got polynomial complexity, now it's O(numOfSubarray * array.length^3) (two array.length for two nested loops and one more because of max(array[previousEnd..newEnd])).

Also we can optimise our algorithm. It makes no sense to always calculate min(array[previousEnd..newEnd]), because previously we did that for newEnd - 1 and we can reuse that value. That brings us to the following algorithm:

for newSubarrayNumber in range(1, numOfSubarray   1):
  for previousEnd in range(0, array.length):
     maxElement = 0
     for newEnd in range(previousEnd   1, array.length   1):
       # maxElement replaces max(array[previousEnd..newEnd]).
       maxElement = max(array[newEnd - 1], maxElement)
       dp[newEnd][newSubarrayNumber] = 
           min(dp[newEnd][newSubarrayNumber],
               dp[previousEnd][newSubarrayNumber - 1]   maxElement)

That's O(numOfSubarray * array.length^2) (just because of loops, no extra complexity multiplier).

I believe one can optimise it even more (maybe using some advanced data structures), feel free to comment. Also even better approach for this particular problem could be some sort of greedy algorithm (like having small subarrays closer to border of an array and one big chunk in the center but that needs to be proven).

CodePudding user response：

We can have O(n^2) by using a dynamic program where the state is (1) the index of the rightmost element considered so far, and (2) the length of the subarray ending at (1).

The information we need to store about those two things is deterministic -- we need the maximum value in subarray (2) and the best solution overall ending at (1).

Then, to consider the next element, we have two choices for each length in (2): either add the element to the subarray, or start a new subarray.

For each element, we would examine O(n) lengths for a total of O(n^2).