Finding pair of non-overlapping subarrays with greatest total sum

Question

This is the question from the interview test paraphrased:

Given is an array and integer K and integer J, each element in the array represents trees planted in a row, the value of the element is the amount of apples that tree has. K and J are the desired amount of consecutive trees that Karen an John want to pick respectively. Karen and Jon are not allowed to pick the same trees. Find the maximum number of apples that can be picked by Karen and John combined.

example:

array: 4 5 7 8 3 1

K: 3

J: 2

Karen picks the first 3 trees and John the next 2, total apples picked is 4 + 5 + 7 = 16 for Karen and 8 + 3 = 11 for John. Together this makes 27 which is the maximum, if John chose the final 2 trees instead of the 2 immediately following Karen he would have picked 4 apples instead of 11, which makes it the wrong solution.

I have one way in theory of solving this, but it involves testing every single possible sum of apples between Karen and John which makes the complexity too much for huge data sets. How would I go about solving this question?

Answer 1

Adding my solution in Python3

def solution(A, K, L) -> int:
    if K + L > len(A):
        return -1
    
    for i in range(1, len(A)):
        A[i] += A[i - 1]

    result, a_max, b_max = A[K + L - 1], A[K - 1], A[L - 1]
    for i in range(K + L, len(A)):
        a_max = max(a_max, A[i - L] - A[i - K - L])
        b_max = max(b_max, A[i - K] - A[i - K - L])
        result = max(result, a_max + A[i] - A[i - L], b_max + A[i] - A[i - K])
    
    return result
    

Answer 2

Ok, so this can be solved with dynamic programming.

• First, we look for John's apples. So, we need to pick 2 consecutive apples. Let's look at the example:

4 5 7 8 3 1

• Ok, so we move from left to right and keep a track of max possible values among the consecutiveness of values of size 2. So, our array would look like,

0 9 12 15 15 15

• Now, we look for Karen's apples from right to left since we already have results for John from left to right. Now, we iterate with 3 consecutive apples from right to left.

• We start with 8 3 1 and value before 8 for John is 12. So sum is 8 + 3 + 1 + 12 = 24. We record it in a max_sum variable.

• We go with 7 8 3. Value for John is 9. So sum is 7 + 8 + 3 + 9 = 27. We record this in max_sum.

• Then we go with 5 7 8 and so on and keep comparing and recording it in max_sum.

• NOTE THAT you also need to make another iteration from right to left for John and left to right for Karen on John's processed data and record the values in max_sum accordingly.

• Print max_sum in the end. Time complexity: O(n), Space complexity is O(n).

Implementation:(following this same LeetCode question)

class Solution {
    public int maxSumTwoNoOverlap(int[] A, int L, int M) {
        int max_val = 0;
        int[] subs = new int[A.length];
        int sum = 0;
        for(int i=0;i<A.length;++i){
            sum += A[i];
            if(i == M-1) subs[i] = sum;
            else if(i > M-1){
                sum = sum - A[i-M];
                subs[i] = Math.max(subs[i-1],sum);
            }
        }
        sum = 0;
        for(int i=A.length-1,j=L-1;i>0;--i,--j){
            sum += A[i];
            if(j <= 0){
                if(j < 0) sum -= A[i+L];                
                max_val = Math.max(max_val,subs[i-1] + sum);
            }
        }

        sum = 0;
        Arrays.fill(subs,0);

        for(int i=A.length-1,j=M-1;i>=0;--i,--j){
            sum += A[i];
            if(j == 0) subs[i] = sum;
            else if(j < 0){
                sum -= A[i+M];
                subs[i] = Math.max(subs[i+1],sum);
            }            
        }
        sum = 0;
        for(int i=0,j=0;i<A.length-1;++i,++j){
            sum += A[i];
            if(j >= L-1){
                if(j >= L) sum -= A[i-L];
                max_val = Math.max(max_val,subs[i+1] + sum);
            } 
        }



        return max_val;
    }
}

Answer 3

Additional assumptions

• All trees have a non-negative number of apples.
• The number of trees, n, is ≤ J + K.
• As such, the optimal strategy is always to take J or K trees, respectively; this is both optimal and possible.
• For two lists, A and B, of sorted numbers (sorted biggest to smallest), the maximum value A_i + B_j-i for 0 ≤ i ≤ j is greater than the maximum value of A_i + B_j-i+1 for 0 ≤ i ≤ j + 1. (This sounds true, but I don't know for certain that it is true because I'm not a good enough mathematician to prove it.)

Approach

The way I'd approach this problem is as follows:

Initial pass, O(n)

Make two passes of the input array, summing each J- / K-long stretch of trees. This produces two arrays, jsum and ksum.

The naïve approach would be to sum anew each time, which would take O(Jn) / O(Kn) time. For bonus points, keep the running total and just add / subtract the two end values as you go along, for a constant two arithmetic operations each time.

Find the highest indices, O(n) at best, O(n²) at worst

For this, I'd use a lazy selection sort on each list to output the best indices . Best case scenario, O(n) when only the first items are needed; worst case, O(n²).

lazy_insertion_sort(a, b, c) sorts a by b[a[i]], so that the first c values of b[a[i]] are the maximum c values; it can safely assume that c - 1 values are already sorted.

Magic, O(n) at best (O(1) excluding lazy_insertion_sort), O(n²) at worst

This algorithm is hard to describe in English.

num_available = 0
jsum_best_indices = [0 ... jsum.length)
ksum_best_indices = [0 ... jsum.length)
while (num_available < n) {
    num_available += 1
    lazy_insertion_sort(jsum_best_indices, jsum, num_available)
    lazy_insertion_sort(ksum_best_indices, ksum, num_available)
    max = -1
    for jbi in [0 ... num_available) {
        kbi = num_available - jbi - 1
        ji = jsum_best_indices[jbi]
        ki = ksum_best_indices[kbi]

        if (ji < ki && ki - ji > J) ||
           (ki < jbi && jbi - kbi > K) {
            candidate = ksum[ki] + jsum[ji]
            if candidate > max {
                max = candidate
            }
        }
    }
    if (max > -1) {
        return max
    }
}
assert false, "The number of trees is too low."

This should always give the best value.

Demo

function first_pass(l, n) {
  var nsum = new Array(l.length - n); // doesn't actually do anything useful; JavaScript is bad.
  
  var running = 0;
  n -= 1;
  for (var i = 0; i < n; ++i) {
    running += l[i];
  }
  for (var i = 0; i < l.length - n; ++i) {
    running += l[i+n];
    nsum[i] = running;
    running -= l[i];
  }
  return nsum;
}

function lazy_insertion_sort(a, b, c) {
  var i, j;
  c -= 1;
  for (i = j = c; i < a.length; ++i) {
    if (b[a[i]] > b[a[j]]) {
      j = i;
    }
  }
  i = a[c];
  a[c] = a[j];
  a[j] = i;
}

function magic(J, K, jsum, ksum, n) {
  var num_available = 0;
  var jsum_best_indices = jsum.map((x,i)=>i);
  var ksum_best_indices = ksum.map((x,i)=>i);
  while (num_available < n) {
    num_available += 1
    lazy_insertion_sort(jsum_best_indices, jsum, num_available)
    lazy_insertion_sort(ksum_best_indices, ksum, num_available)
    var max = -1;
    for (var jbi = 0; jbi < num_available; jbi += 1) {
      var kbi = num_available - jbi - 1;
      var ji = jsum_best_indices[jbi];
      var ki = ksum_best_indices[kbi];

      if ((ji < ki && ki - ji > J) ||
          (ki < jbi && jbi - kbi > K)) {
        var candidate = ksum[ki] + jsum[ji]
        if (candidate > max) {
          max = candidate;
        }
      }
    }
    if (max > -1) {
        return max;
    }
  }
  throw "The number of trees is too low.";
}

document.getElementById("run").addEventListener("click", function () {
  var J = +document.getElementById("J").value;
  var K = +document.getElementById("K").value;
  var l = eval(document.getElementById("array").value);
  
  var jsum = first_pass(l, J);
  var ksum = first_pass(l, K);
  document.getElementById("output").innerText = magic(J, K, jsum, ksum, l.length);
});

Array: <input id="array" value="[1, 1, 1, 2, 2, 5, 6, 7, 5, 2, 2, 3, 1, 1, 1]"/><br />
J: <input id="J" type="number" value="3" /><br />
K: <input id="K" type="number" value="4" /><br />
<button id="run">Run</button>

Output: <span id="output"></span>

This JavaScript code should be deemed pseudocode; I haven't invoked the niceties of JavaScript required to get everything reasonable to run at a decent speed.

Answer 4

Let f(i) represent the best choice up to index i. Then:

f(i) = max(
  // Karen after John
  kr(i) + jl(i - K),

  // Karen before John
  kl(i) + jr(i + 1)
)

where kr is the best K-length
      window from the right;

      kl is the best K-length
      window from the left;

      similarly for jl, jr

Answer 5

In the stress and the hurry of an interview, I would get, for each K sets of trees the best J set of trees available.

The final result would be the best pair obtained.

This is far from being a good algorithm, but it works, in O((N - K) * (N - J)) complexity

let array = [4, 5, 7, 8, 3, 1];
let K = 3;
let J = 2;

// An apple a day keeps the doctor away as long as you aim well
function ILoveApples(arr, k, j)
{
  // total apples gathered
  let total = 0;
  // get each K sets
  for (let i = 0; i + k < arr.length; ++i)
  {
    // get the count of apples for the current K set
    let kApples = arr.slice(i, i + k).reduce((a, c) => a + c);
    // no count for the J set yet
    let jApples = 0;
    
    // get each J sets
    for (let l = 0; l + j < arr.length; ++l)
    {
      // Avoid overlapping of sets
      if (i >= l + j || i + k <= l)
      {
        // get the count of the current J set
        let temp = arr.slice(l, l + j).reduce((a, c) => a + c);
        // Get the best  J set for that current K set
        if (temp > jApples)
          jApples = temp;
        
      }
    }
    //get the total and save it if better than the previous best total
    if (kApples + jApples > total)
    {
      total = kApples + jApples;
    }
  }
  return total;
}

console.log(ILoveApples(array, K, J));

Answer 6

I would first prepare an array containing the cumulative sum of the number of apples.

i.e. [4,5,7,8,3,1] -> [4,4+5,4+5+7,4+5+7+8,4+5+7+8+3,4+5+7+8+3+1].

The benefit of this is that it allows you to compute the sum of any subarray by performing a single subtraction.

This can be computed in O(n) operations by keeping a running total and adding on the next element each time.

Next use this to compute the answer f(y) to "What is the amount of apples that Karen gets from picking at position y?" for each value of y.

Then consider solving the question "What is the maximum amount of apples if John picks from position x and Karen chooses the best position that does not overlap?" We can easily compute the number of apples that John gets with a subtraction, and then we need to add on the best for Karen. This best will be the maximum of f(y) for all legal values of y. This is also easy to compute by preparing an array g(z) which is the maximum of f(y) for all y less than equal to z, and h(z) which is the maximum of f(y) for all y greater than or equal to z.

Overall this computes the optimum with O(n) complexity and O(n) space.