Найти максимальную сумму непрерывного подмассива, когда можно опустить не более k элементов?

Question

Например, n=10
arr[]={6,-5,3,-7,6,-1,10,-8,-8, 8}
For k=0, best segment is 5-7 with sum=15. For k=2, best segment is 1-7 with sum=24. For k=6, best segment is 1-10 with sum=33.
По заданному массиву и k найти сумму.

Я думаю, пусть dp[i][j] обозначает максимальный сегмент, заканчивающийся в позиции i, в которой не более j элементов выпало. Индуктивное вычисление dp[i][j] из dp[i][j-1]. Но как отследить элементы, удаленные из dp[i][j-1], и не удалять их снова ??? Я запутался в проблемах с дп. Я хочу знать подход дп и какой-то другой подход, если это возможно?

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