logo标签列表

寻找具有最大总和的不重叠子数组对

arraysalgorithm
6
这是面试测试问题的释义：
给定一个数组和整数K、J，数组中的每个元素表示种植在一排中的树木，元素的值是该树木所拥有的苹果数量。K和J分别是Karen和John想要采摘的连续树木的数量，他们不能采摘相同的树木。找到Karen和John组合能够采摘的最大苹果数。
例子： 数组：4 5 7 8 3 1 K：3 J：2 Karen选取前3棵树，John选取接下来的2棵，总共采摘的苹果数为4+5+7=16作为Karen的组合和8+3=11作为John的组合。两者合计27是最大值。如果John选择最后2棵树而非紧随Karen之后的2棵树，他将只采摘了4个苹果，这不是正确的解决方案。
我有一种理论上的解决方法，但它涉及到测试Karen和John之间每一个可能的苹果数的总和，这使得复杂度对于巨大的数据集来说过高。我应该如何解决这个问题？
1
我不确定这个问题是否适合在 Stack Overflow 上。我认为应该可以，所以我会写一个回答，但我并不确定。请先阅读 [导览]（tour）。 （编辑：是的，这个问题是适合的。） - wizzwizz4
6个回答
1

让 f(i) 表示到索引 i 的最佳选择。则：

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
1

好的，这可以用动态规划来解决。

  • 首先，我们要找到约翰的苹果。所以，我们需要选择2个连续的苹果。让我们看一个例子:

4 5 7 8 3 1

  • 好的，所以我们从左到右移动，并在大小为2的值的连续性中保持最大可能的值跟踪。所以，我们的数组看起来像这样,

0 9 12 15 15 15

现在，我们从右到左查找Karen的苹果，因为我们已经有了John从左到右的结果。现在，我们从右向左迭代3个连续的苹果。 我们从8 3 1开始，John之前的值为12。所以总和是8 + 3 + 1 + 12 = 24。我们将其记录在max_sum变量中。 我们接着用7 8 3。John的值为9。所以总和是7 + 8 + 3 + 9 = 27。我们将其记录在max_sum中。 然后我们用5 7 8等进行比较，并在max_sum中记录它们。 请注意，您还需要对处理过的John的数据进行从右到左的另一次迭代，对Karen的数据进行从左到右的迭代，并相应地在max_sum中记录值。 最后打印max_sum。时间复杂度为O(n)，空间复杂度为O(n)。

实现：(遵循同样的LeetCode问题)

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;
    }
}
如果Karen和John选择的树木组不是直接相邻的，那么它将如何工作呢？因此，如果Karen选择前三棵树，而John选择最后两棵树，那么K和J不需要彼此相邻，只需要在每个组内选择连续的树木即可。 - Simon Lombard
@SimonLombard 这会起作用，因为我们已经在John的数组中收集了给定范围内的最大值结果。当然，对于Karen和John的选择不需要彼此连续。 - nice_dev
vivek_23和@SimonLombard，这不是我之前发布过的吗？ - גלעד ברקן
@גלעדברקן 我在写答案的时候没有看到（而且那时页面是未激活的）。此外，我想逐步用文字解释这个问题。 - nice_dev
1
@vivek_23 动态规划是你向我介绍的重要概念，谢谢。 - Simon Lombard
@SimonLombard 很高兴能帮助你 :) 我希望我已经解决了你最初的疑惑。 - nice_dev
1

额外假设

  • 所有的树都有非负数量的苹果。
  • 树的数量 n ≤ J + K。
  • 因此，最佳策略始终是分别采摘J或K棵树；这既是最优的，也是可行的。
  • 对于两个已排序数字列表A和B（从大到小排序），当0 ≤ i ≤ j时，最大值Ai + Bj-i 大于 0 ≤ i ≤ j + 1 时的最大值Ai + Bj-i+1。（听起来是真的，但我不能确定它是否正确，因为我不够擅长数学证明。）

方法

我处理这个问题的方法如下：

初始遍历，O(n)

对输入数组进行两次遍历，汇总每个J- / K-长的树木区间。这将产生两个数组，jsum 和 ksum。

朴素的方法是每次重新求和，这需要O(Jn) / O(Kn) 的时间。为了额外加分，保持运行总数，并在沿途添加/减去两个末尾值，每次进行两个算术操作。

查找最高指数，最好情况下O(n)，最坏情况下O(n²)

为此，我会在每个列表上使用懒惰选择排序来输出最佳索引。最好情况下，只需要第一个项目时，O(n)；最坏情况下，O(n²)。

lazy_insertion_sort(a, b, c)会按照b[a[i]]的值来对a进行排序，以便b[a[i]]的前c个值是最大的c个值；它可以安全地假设已经有c-1个值已经排序好了。

神奇的算法，最好情况下为O(n)，最坏情况下为O(n²)（不包括lazy_insertion_sort的O(1)）

这个算法很难用英语描述。

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."

这个标记应该始终提供最佳值。

演示

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>

这段 JavaScript 代码应该被视为伪代码；我没有调用 JavaScript 的方便之处，以使一切合理地以较快的速度运行。
1
我会首先准备一个包含苹果数量的累加和数组。
例如：[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]。
这样做的好处是可以通过执行一次减法来计算任何子数组的总和。
通过保持运行总数并每次添加下一个元素，可以在O(n)操作中计算出这个数组。
接下来，使用此方法计算答案f(y)，即“Karen在位置y采摘了多少苹果？”对于每个y值。
考虑解决问题“如果John从位置x选择，Karen选择不重叠的最佳位置，那么最多能摘多少个苹果？” 我们可以通过减法轻松计算John得到的苹果数，然后我们需要加上Karen的最佳选择。这个最佳选择将是所有合法值y的f(y)的最大值。这也很容易通过准备一个数组g(z)，其中z小于等于y时f(y)的最大值，以及h(z)，其中z大于等于y时f(y)的最大值来计算。
总体而言，这样可以在O(n)复杂度和O(n)空间下计算出最优解。
1
我认为这不正确。反例：当J=3和K=4时，111225675223111。 - wizzwizz4
1
在面试的紧张和匆忙中，我会为每个K组树获取最佳的J组可用树。最终结果将是获得的最佳配对。这远非是一个好的算法，但它可以在O((N-K)*(N-J))的复杂度下运行。 

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));

这个可以工作，但是我担心在处理大型数据集时会变得过于复杂 :( - Simon Lombard
0

在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
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接