Cách nhanh nhất để tìm phạm vi tổng tối đa trong int []

Question

Đã tối ưu hóa một thuật toán và đi xuống phần cuối cùng. Tôi có một mảng các số nguyên như thế này:

[1, 1, 2, 5, 0, 5, 3, 1, 1]

yêu cầu của tôi là như sau:

1. đầu vào: số lượng số nguyên để tổng hợp trên
2. tổng max nên bao gồm các số nguyên cạnh nhau
3. nếu một số nguyên có giá trị 0 tổng trong phạm vi này sẽ bị vô hiệu
4. tổng tối đa của các số nguyên và chỉ số của mỗi số nguyên được trả về

kết quả dự kiến:

đầu vào Với 2 (2 muốn) với mảng như đã đề cập nên do trở [8, [ 5, 6]] trong đó 8 là tổng số nguyên tại chỉ số 5 và 6

Cho đầu vào của 3 (3 muốn) với mảng như đã đề cập nên trả lại [9, [5, 6, 7]] trong đó 9 là tổng của các số nguyên tại chỉ số 5, 6 và 7 (lưu ý rằng mặc dù các số nguyên tại các chỉ mục 3, 4, 5 có tổng t cao hơn kết quả là không hợp lệ do chỉ số 4 là 0)

Tôi hiện đang quản lý điều này bằng cách thực hiện nhiều vòng lặp, nhưng tự hỏi liệu có ai đó có cách nào tốt hơn để đạt được điều này hay không. Ngôn ngữ lập trình lựa chọn của tôi hiện là C# - Tôi sẽ đánh giá cao nếu các câu trả lời có thể có trong C#. Bất kỳ việc sử dụng LINQ và các tính năng Math ưa thích khác đều miễn là nó là cách nhanh nhất.

Answer 1

Tôi nghĩ bạn có thể giải quyết vấn đề này theo thời gian tuyến tính. Đầu tiên, thay thế tất cả 0 bằng một số rất nhỏ (ví dụ: -2^30) để nó không ảnh hưởng đến tổng của chúng ta.

Sau đó:

let s[i] = sum of first i integers 
let k = number of integers required 
let max = -inf  
for (int i = k; i <= N; ++i) 
    if (s[i] - s[i - k - 1] > max) 
    max = s[i] - s[i - k - 1] 

Bạn có lẽ có thể tránh thay thế số không với một vài điều kiện thêm. nếu s [i] = tổng của số nguyên i đầu tiên, thì s [i] - s [k - 1] cho bạn tổng các số nguyên k qua i.

Chỉnh sửa: Bạn có thể thực hiện điều này trong O (1) khoảng trống thừa như sau: đầu tiên thay thế tất cả 0.

thì:

max = cr = sum of first k integers. 
for (int i = k + 1; i <= N; ++i) 
{ 
    cr = cr + numbers[i] - numbers[i - k] 
    if (cr > max) 
    max = cr; // also update positions 
} 

Để tránh thay thế zero trong dung dịch đầu tiên, chỉ cần bỏ qua không gian k trước khi gặp phải một số không. Trong giải pháp thứ hai, bỏ qua k hoặc k + 1 (phụ thuộc vào cách bạn chọn để triển khai trường hợp đặc biệt này) các khoảng trống phía trước, nhưng hãy chắc chắn xây dựng lại biến số cr của bạn khi thực hiện bỏ qua!

Answer 2

Mã bên dưới nên thực hiện thủ thuật. Hiệu suất sẽ phụ thuộc vào kích thước của phạm vi được tính tổng. Càng nhiều elemnts càng tốt thì nó sẽ thực hiện so với ngây thơ của việc thêm một tập hợp con trong mỗi lần lặp lại

int getSum(int[] arr, int wanted) 
     { 
      var pre = new int[arr.Length]; 
      pre[0] = 0; 
      pre[1] = arr[0]; 
      int max = 0; 
      int skip = 1; 
      for (var i = 1; i < arr.Length; i++) 
      { 
       skip--; 
       //if the sum is marked invalid with a zero skip 
       var current = arr[i]; 
       //calculate the index once 
       int preIndex = i + 1; 
       if (current == 0) 
       { 
        skip = wanted; 
        pre[preIndex] = pre[i]; 
        continue; 
       } 
       //store the sum of all elements until the current position 
       pre[preIndex] = pre[i] + current; 
       //find the lower end of the range under investigation now 
       var lower = i - wanted; 
       //if we haven't reached the wanted index yet we have no sum or if 
       //it's less than wanted element since we met a 0 
       //just go to the next element 
       if (lower < 0 || skip > 0) 
        continue; 
       var sum = pre[preIndex] - pre[lower]; 
       if (sum > max) 
        max = sum; 
      } 
      return max; 
     } 

Answer 3

Sau đây là một rant, và hoàn toàn chưa được kiểm tra. Thậm chí không chắc chắn nếu nó sẽ biên dịch.Tôi để nó cho người khác để cải thiện nó.

using System; 
using System.Linq; 
public int[] max(int[] a, int amount) { 
    var max = int.MinValue; 
    var maxPos = 0; 
    if (a.length < amount) return null; 
    var c = 0; 
    while (c == 0) { 
     for (int i = 0; i < amount; i++) { 
      if (a[i + maxPos] == 0) { 
       c = 0; 
       break; // try again 
      } 
      c += a[i]; 
     } 
     if (c != 0) maxPos = i - amount; 
    } 
    if (c == 0) return null; 
    max = c; 
    for (int i = maxPos; i + amount < a.length; i++) { 
     if(a[i] == 0) { 
      i += amount - 1; 
      continue; 
     } 
     c -= a[i]; 
     c += a[i + amount]; 
     if (c > max) { 
      c = max; 
      maxPos = i; 
     } 
    } 
    if (c == 0) return null; 
    var result = new int[amount + 1]; 
    result[0] = max; 
    for (int i = 0; i < amount; i++) 
     result[i + 1] = maxPos + i; 
    return result; 
} 

Answer 4

Mã "dễ đọc" được coi là "tối ưu hóa"?

int numberOfElements = 4; //parameter 
int[] numbers = new[] { 1, 1, 2, 5, 0, 5, 3, 1, 1 }; //numbers 


int[] result = 
    //cicle each element 
    (from n in Enumerable.Range(0, numbers.Length - numberOfElements + 1) 
    //keep the (n + numberOfElements) elements 
    let myNumbers = from p in Enumerable.Range(n, numberOfElements) 
        select numbers[p] 
    //keep the sum (if we got a 0, sum is 0) 
    let sum = myNumbers.Contains(0) ? 0 : myNumbers.Sum() 
    orderby sum descending  //order by sum 
    select myNumbers)   //select the list 
     .First().ToArray();  //first is the highest 

Cân nhắc thêm .AsParallel() để có hiệu suất khi .NET 4 hết.

Answer 5

Idea là 1. Chia mảng cho các nhóm để đo tổng 2. Đếm tiền cho mỗi nhóm 3. Hình ra max tổng

Dưới đây là đoạn code

private Result GetMax(ICollection<int> items, int itemCount) 
{ 
    return items. 
    Take(items.Count - (itemCount - 1)). 
    Select((value, index) => items.Skip(index).Take(itemCount)). 
    Select((group, index) => 
     new Result 
     { 
     Index = index, 
     Sum = group.Aggregate(0, (sum, i) => sum + (i == 0 ? int.MinValue : i)) 
     }). 
    Max(); 
} 

private struct Result : IComparable<Result> 
{ 
    public int Index { get; set; } 
    public int Sum { get; set; } 

    public int CompareTo(Result other) 
    { 
    return Sum.CompareTo(other.Sum); 
    } 
} 

Answer 6

này là O (n) thời gian và O (1) không gian và chỉ đi một lần thông qua mảng.

static public int[] FindMaxSumRange(int[] data, int n) 
{ 
    // two pointers showing the lower and upper bound of current running sum 
    int upper = 0, lower = 0; 
    // best result found yet 
    int max_found = 0; 
    int max_position = -1; 

    while (lower <= data.Length - n) { 
     int running_sum = 0; 
     // prefill running sum with n items 
     for (upper = lower; upper - lower < n && upper < data.Length; upper++) { 
      if (data[upper] == 0) { 
       // found a zero, set lower pointer to the next item 
       lower = upper + 1; 
       break; 
      } 
      running_sum += data[upper]; 
     } 
     if (upper - lower != n) { 
      // found a zero, restart at new lower position 
      continue; 
     } 
     if (running_sum > max_found) { 
      max_found = running_sum; 
      max_position = lower; 
     } 
     while (upper < data.Length) { 
      if (data[upper] == 0) { 
       // found a zero, set lower pointer to the next item 
       lower = upper; 
       break; 
      } 
      running_sum += data[upper] - data[lower]; 
      if (running_sum > max_found) { 
       max_found = running_sum; 
       max_position = lower; 
      } 
      upper++; lower++; 
     } 
     lower++; 
    } 
    return new int[]{max_found, max_position}; 
} 

Trả về số tiền tối đa này và vị trí được tìm thấy tại. Nếu bạn cần có danh sách các chỉ mục, chỉ cần tạo phạm vi [max_position, max_position + n)