如何才能找到最大子集的最大差异为5的大小？

Question

我有一个数组数组，我试图找到最大子集的大小，使得子集中的所有数字相距小于5。如有必要，他们可以假设进行了排序。

例如：

[1, 2, 5, 6, 8, 9, 15] 

4是最大的子集。 （5,6,8,9）

我希望有一个简单的LINQ答案，但我没有想到它。我可以对它进行排序，然后用每个起始数字遍历它，跟踪该数字中的最多数量，但这看起来非常难看，效率低下。有任何想法吗？

---

澄清什么，我想避免：

(1,2,5) - 3 
(2,5,6) - 3 
(5,6,8,9) - 4 
(6,8,9) - 3 
(8,9) - 2 
(9) - 1 
(15) - 1 

Answer 1

这个问题可以通过维护两个指针left和right来解决。

假设您有一个排序数组array的n数字。

left = 0 
right = 0 
ans = INT_MIN 
while right == n : 
    if array[right] - array[left] < 5: 
     right++ 
    else: 
     left++ 
    ans = max(right - left + 1, ans) 

Answer 2

首先在排序列表的开始处设置最大可能集。然后继续从前面删除值，直到下一个值适合，并在下一个值之后添加尽可能多的值。这使得一套新的。在任何特定时刻保持最大的跟踪。

像这样的东西在C＃中：作为

static IEnumerable<T[]> CloseSublists<T>(this IEnumerable<T> values, Func<T, T, bool> isClose) where T : IComparable<T> { 
    var window = new Queue<T>(); 
    var enumerator = values.GetEnumerator(); 

    if (!enumerator.MoveNext()) { 
     return; 
    } 

    bool more; 

    do { 
     window.Enqueue(enumerator.Current); 
    } while ((more = enumerator.MoveNext()) && isClose(window.Peek(), enumerator.Current)); 

    yield return window.ToArray(); 

    while (more) { 
     do { 
      window.Dequeue(); 
     } while (window.Count != 0 && !isClose(window.Peek(), enumerator.Current)); 

     do { 
      window.Enqueue(enumerator.Current); 
     } while ((more = enumerator.MoveNext()) && isClose(window.Peek(), enumerator.Current)); 

     yield return window.ToArray(); 
    } 
} 

和

public static T MaxBy<T, TKey>(this IEnumerable<T> items, Func<T, TKey> key) where TKey : IComparable<TKey> { 
    var enumerator = items.GetEnumerator(); 
    enumerator.MoveNext(); 

    var max = enumerator.Current; 
    TKey maxKey = key(max); 

    while (enumerator.MoveNext()) { 
     T current = enumerator.Current; 
     TKey currentKey = key(current); 
     int relation = currentKey.CompareTo(maxKey); 

     if (relation > 0) { 
      max = current; 
      maxKey = currentKey; 
     } 
    } 

    return max; 
} 

：

int[] x = {1, 2, 5, 6, 8, 9, 15}; 
x.CloseSublists((a, b) => b < a + 5).MaxBy(l => l.Length) 

Answer 3

基于王子的回答，我把它改写成C＃和改进一点：

protected int MaxSubLen(int[] arr, int diffLessThan) 
{ 
    int l = 0, r = 0; 
    while (r < arr.Length) 
    { 
     if (arr[r] - arr[l] >= diffLessThan) 
     { 
      ++l; 
     } 
     ++r; 
    } 
    return r - l; 
} 

和，只是为了好玩，返回通用版本序列：

protected IEnumerable<T> MaxSubarray<T>(IList<T> arr, Func<T, T, bool> isClose_L_R) 
{ 
    int l = 0, r = 0, start = 0; 
    while (r < arr.Count) 
    { 
     if (isClose_L_R(arr[l], arr[r])) 
     { 
      start = l; 
     } 
     else 
     { 
      ++l; 
     } 
     ++r; 
    } 
    for (int i = start; i < start + r - l; ++i) 
    { 
     yield return arr[i]; 
    }; 
}