具有所有相同元素的最长子数组的长度

Question

我有这个问题:

您将获得一个整数 A 和一个整数 k 的数组。您可以将 A 的元素递减到 k 次，目标是生成一个元素都相等的连续子数组。返回可以用这种方式生成的最长的连续子数组的长度。

例如，如果 A 是 [1，7，3，4，6，5] 并且 k 是 6，那么您可以生成 [1，7，3，4-1，6-1-1-1，5-1-1] = [1，7，3，3，3，3]，因此您将返回 4。

最佳解决方案是什么？

Answer 1

def cost(a, i, j):
  n = j - i 
  s = 0
  m = a[i]
  for k in range(i,j):
    s += a[k]
    m = min(m, a[k])
  return s - n * m;

def solve(n,k,a):
 m=1
 for i in range(n):
  for j in range(i,n+1):
   if cost(a,i,j)<=k:
    x = j - i 
    if x>m:
     m=x
 return m

这是我的python3解决方案，符合您的规范。

Answer 2

子数组必须等于其最低成员，因为唯一允许的操作是减少（减少最低成员会增加不必要的成本）。给定：

a1, a2, a3...an

要降低的成本是：

sum(a1..an) - n * min(a1..an)

例如

3, 4, 6, 5
sum = 18
min = 3
cost = 18 - 4 * 3 = 6

将复杂度从 O（n^2） 降低到对数因子的一种方法是：对于每个元素作为候选最佳子数组的最右边（或最左边）元素，二叉搜索成本内的最长长度。为此，我们只需要总和，我们可以从 O（1） 中的前缀总和、长度（我们已经在搜索）和最小范围查询中获得，这是经过充分研究的。

作为对这篇文章下面的评论的回应，这里有一个演示，当我们从最右边的每个元素扩展一个子数组时，成本序列单调增加，因此可以用二分搜索法查询。

JavaScript代码：

function cost(A, i, j){
  const n = j - i + 1;
  let sum = 0;
  let min = Infinity;
  for (let k=i; k<=j; k++){
    sum += A[k];
    min = Math.min(min, A[k]);
  }
  return sum - n * min;
}

function f(A){
  for (let j=0; j<A.length; j++){
    const rightmost = A[j];
    const sequence = [];
    
    for (let i=j; i>=0; i--)
      sequence.push(cost(A, i, j));
    
    console.log(rightmost + ': ' + sequence);
  }
}

var A = [1,7,3,1,4,6,5,100,1,4,6,5,3];

f(A);