如何才能找到最大子集的最大差異爲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]; 
    }; 
}