algorithm - 当最多可以省略 k 个元素时，查找最大和连续子数组？

Question

例如- n=10
arr[]={6,-5,3,-7,6,-1,10,-8,-8, 8}
对于 k=0，最佳片段是 5-7，sum=15。
对于 k=2，最佳片段是 1-7，sum=24。
对于 k=6，最佳段是 1-10，sum=33。
给定数组和 k，求和。

我认为，让 dp[i][j] 表示在位置 i 结束的最大段，最多删除 j 个元素。从 dp[i][j-1] 归纳计算 dp[i][j]。但是如何跟踪从 dp[i][j-1] 中删除的元素而不是再次删除它们？？？我对 dp 问题感到困惑。如果可能，我想知道 dp 方法和其他一些方法？

Answer 1

令 m(i, j) 表示以索引 i 结尾的最大总和，恰好有 k 遗漏。然后

m(i, j) = max(
  // Use A[i-1]
  // (same number of omissions: j)
  A[i-1] + max(0, m(i - 1, j)),

  // Omit A[i-1]
  // (reference j-1 since we are
  // adding an omission here)
  m(i - 1, j - 1)
)

为了得到最多 k 遗漏的答案，我们考虑了所有不同的精确k 的结果。 (请注意，空间仍然可以减少到 O(n)，因为只需要前一行和当前行。)

JavaScript 代码:

function f(A, k){
  console.log(`Input: ${ JSON.stringify(A) }\n\n`);

  let m = new Array(A.length + 1);
  
  let result = 0;

  // Initialize Array
  for (let i=0; i<=A.length; i++)
    m[i] = new Array(k + 1).fill(0);

  // Zero omissions (Kadane's algorithm)
  for (let i=1; i<=A.length; i++){
    m[i][0] = A[i-1] + Math.max(0, m[i-1][0]);
    result = Math.max(result, m[i][0]);
  }
  
  for (let i=1; i<=A.length; i++){
    for (let j=1; j<=k; j++){
      m[i][j] = Math.max(
        A[i-1] + Math.max(0, m[i-1][j]),
        m[i-1][j-1]
      );
      
      result = Math.max(result, m[i][j]);
    }
  }
  
  for (let row of m)
    console.log(JSON.stringify(row));
    
  return result;
}

let A = [6, -5, 3, -7, 6, -1, 10, -8, -8, 8];
let k = 6;

console.log(f(A, k));