Số tiền tối đa của tất cả các mảng phụ có kích thước k cho mỗi k = 1..n

Question

Cho một mảng có kích thước n, cho mỗi k từ 1 đến n, tìm số tiền tối đa của mảng con tiếp giáp có kích thước k.

Sự cố này có giải pháp rõ ràng với độ phức tạp thời gian O (N) và không gian O (1). Mã Lua:

array = {7, 1, 3, 1, 4, 5, 1, 3, 6} 
n = #array 

function maxArray(k) 
    ksum = 0 
    for i = 1, k do 
     ksum = ksum + array[i] 
    end 
    max_ksum = ksum 
    for i = k + 1, n do 
     add_index = i 
     sub_index = i - k 
     ksum = ksum + array[add_index] - array[sub_index] 
     max_ksum = math.max(ksum, max_ksum) 
    end 
    return max_ksum 
end 

for k = 1, n do 
    print(k, maxArray(k)) 
end 

Có thuật toán nào có độ phức tạp thấp hơn không? Ví dụ, O (N log N) + bộ nhớ bổ sung.

chủ đề liên quan:

• Kadane's algorithm

Answer 1

dưới đây quá trình có thể giúp bạn

1) Chọn các yếu tố k đầu tiên và tạo ra một Self-Balancing Binary Search Tree (BST) của kích thước k .

2) Chạy một vòng lặp for i = 0 đến n - k

... ..a) Lấy yếu tố tối đa từ BST, và in nó.

… ..b) Tìm kiếm arr [i] trong BST và xóa nó khỏi BST.

… ..c) Chèn arr [i + k] vào BST.

Độ phức tạp của thời gian: Độ phức tạp của bước 1 là O (kLogk). Độ phức tạp theo thời gian của các bước 2 (a), 2 (b) và 2 (c) là O (Logk). Vì các bước 2 (a), 2 (b) và 2 (c) nằm trong vòng lặp chạy n-k + 1 lần, độ phức tạp thời gian của thuật toán hoàn chỉnh là O (kLogk + (n-k + 1) * Logk) cũng có thể được viết là O (nLogk).

Answer 2

Tôi không nghĩ rằng có một giải pháp hiệu quả hơn O (N²) nếu bạn không thêm bất kỳ ràng buộc nào khác. Nói cách khác, không có cách nào khác để quyết định bạn đã tìm thấy subarray tổng tối đa nhưng để khám phá tất cả các subarrays khác.

Do đó, giải pháp kém phức tạp bao gồm O (n ²/2) là tổng số subarrays tiếp giáp của một mảng có độ dài cho N.

Cá nhân tôi sẽ thực hiện điều này với cách tiếp cận lập trình năng động. Ý tưởng là có một nêm kết quả một phần, và sử dụng chúng để xây dựng các khoản tiền hiện tại của các subarrays (thay cho tính toán toàn bộ số tiền thông qua). Nhưng dù sao điều này cho phép "chỉ" một tốc độ không đổi, do đó độ phức tạp là O (N²/2) ~ O (N²).

Sau đây là giả - xin lỗi vì đã không nói Lua

// here we place temporary results, row by row alternating in 0 or 1 
int[2][N] sum_array_buffer 
// stores the start of the max subarray 
int[N] max_subarray_start 
// stores the value 
int[N] max_subarray_value 

array = {7, 1, 3, 1, 4, 5, 1, 3, 6} 
// we initialize the buffer with the array (ideally 1-length subarrays) 
sum_array_buffer[1] = array 
// the length of subarrays - we can also start from 1 if considered 
for k = 1 ; k <= (N); ++k: 
    // the starting position fo the sub-array 
    for j = 0; j < (N-k+1); ++j: 
     sum_array_buffer[k%2][j] = sum_array_buffer[(k+1)%2][j] + array[j+k-1] 
     if j == 0 || sum_array_buffer[k%2][j] > max_subarray_value[k]: 
      max_subarray_value = sum_array_buffer[k%2][j] 
      max_subarray_start[k] = j 


for k = 1 ; k <= (N); ++k: 
    print(k, max_subarray_value[k]) 

Graphycally:

Answer 3

Chúng tôi tạo ra một Dequeue, Qi công suất k, mà các cửa hàng chỉ yếu tố hữu ích của cửa sổ hiện tại k yếu tố. Một phần tử hữu ích nếu nó ở trong cửa sổ hiện tại và lớn hơn tất cả các phần tử khác ở bên trái của nó trong cửa sổ hiện hành. Chúng tôi xử lý tất cả các phần tử mảng từng cái một và duy trì Qi để chứa các phần tử hữu ích của cửa sổ hiện tại và các thành phần hữu ích này được duy trì theo thứ tự sắp xếp. Phần tử ở phía trước của Qi là phần tử lớn nhất ở phía sau của Qi là cửa sổ nhỏ nhất hiện tại.