Length of Longest Subarray with all same elements

user_14788564 0
Viewed 889

I have this problem:

You are given an array of integers A and an integer k. You can decrement elements of A up to k times, with the goal of producing a consecutive subarray whose elements are all equal. Return the length of the longest possible consecutive subarray that you can produce in this way.

For example, if A is [1,7,3,4,6,5] and k is 6, then you can produce [1,7,3,4-1,6-1-1-1,5-1-1] = [1,7,3,3,3,3], so you will return 4.

What is the optimal solution?

algorithm
2 Answers

The subarray must be made equal to its lowest member since the only allowed operation is reduction (and reducing the lowest member would add unnecessary cost). Given:

a1, a2, a3...an

the cost to reduce is:

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

For example,

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

One way to reduce the complexity from O(n^2) to a log factor is: for each element as the rightmost (or leftmost) element of the candidate best subarray, binary search the longest length within cost. To do that, we only need the sum, which we can get from a prefix sum in O(1), the length (which we are searching on already), and minimum range query, which is well-studied.

In response to comments below this post, here is a demonstration that the sequence of costs as we extend a subarray from each element as rightmost increases monotonically and can therefore be queried with binary search.

JavaScript code:

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

user_20347870 
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

This is my python3 solution as per your specifications.

user_125125560
Related