Hình chữ nhật tối đa tổng trong một ma trận thưa thớt

Question

Tìm hình chữ nhật tối đa trong một ma trận NxN có thể được thực hiện trong O(n^3) thời gian sử dụng thuật toán 2-d kadane, như được chỉ ra trong các bài đăng khác. Tuy nhiên, nếu ma trận thưa thớt, cụ thể là O(n) các mục nhập khác 0, thời gian O(n^3) có bị đánh bại không?

Nếu nó giúp, cho ứng dụng hiện tại tôi quan tâm, nó sẽ đủ để có một giải pháp mà giả định nhiều nhất một giá trị khác không trong mỗi hàng và trong mỗi cột của ma trận. Tuy nhiên, trong các ứng dụng trong tương lai giả định này có thể không phù hợp (chỉ là thưa thớt sẽ giữ), và dù sao trực giác toán học của tôi là có thể có giải pháp tốt mà chỉ cần khai thác thưa thớt và không khai thác thêm thực tế là ma trận một sản phẩm của một đường chéo và một ma trận hoán vị.

Answer 1

Có, nó có thể được thực hiện tốt hơn.

Trước hết, chúng ta hãy suy nghĩ về một cấu trúc dữ liệu cho phép chúng ta

1. Cập nhật bất kỳ giá trị duy nhất của mảng 1D tiềm ẩn trong O(logn) thời gian
2. Tìm tổng của subarray tối đa của mảng trong O(1) thời gian

Thực ra, một cây nhị phân cân bằng trông giống như dưới đây có thể thực hiện công việc. Cấu trúc cây có thể được mô tả là:

1. Mỗi nút lá của cây đại diện cho mọi phần tử của mảng.
2. Nếu một nút bên trong bao gồm phạm vi [a, b], con trái của nó bao phủ phạm vi [a, c] và con phải của nó bao phủ phạm vi [c + 1, b], trong đó c = floor((a + b)/2)).

3. Nút gốc bao gồm phạm vi [1, n].

        O 
           / \ 
          /  \ 
          /   \ 
         /    \ 
         /     \ 
         O      O 
        / \     / \ 
       / \    / \ 
       /  \    /  \ 
       O   O   O   O 
   /\  /\  /\  /\ 
   o  o  o  o  o  o  o  o 
   A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] 
   

Có 4 lĩnh vực gắn liền với mỗi nút v (bao gồm cả các nút lá và các nút nội bộ):

• S[v]: tổng của tất cả các giá trị trong phạm vi v 's
• M[v] : tổng số chi tiết phụ tối đa trong phạm vi của v của
• L[v]: tổng của maximu m subarray rằng bắt đầu từ phía bên trái của v 'phạm vi s
• R[v]: tổng của subarray tối đa mà kết thúc vào phía bên phải của v' phạm vi s

Dựa trên các định nghĩa trên, chúng ta có thể tìm ra quy tắc cập nhật sau:

• Đối với bất kỳ nút lá v, S[v] = A[v], M[v] = L[v] = R[v] = max{0, A[v]}
• Đối với bất kỳ nút nội v và con của nó l và r,
  
  • S[v] = S[l] + S[r]
  • M[v] = max{M[l], M[r], R[l] + L[r]}
  • L[v] = max{L[l], L[r] + S[l]}
  • R[v] = max{R[r], R[l] + S[r]}

Cuối cùng, chúng ta có thể thực hiện các hoạt động nêu ở phần đầu.

• Để cập nhật A[i], chúng tôi có thể tìm thấy nút lá tương ứng trên cây và cập nhật các trường dọc theo đường dẫn tới gốc bằng các quy tắc trên.
• Tổng chi phí con tối đa chỉ đơn giản là M[root].

Bây giờ, hãy thảo luận cách tìm hình chữ nhật tối đa bằng cấu trúc dữ liệu này. Nếu chúng ta sửa hàng trên và hàng dưới của hình chữ nhật thành các hàng thứ 1, i và j thì vấn đề sẽ trở thành vấn đề tổng hợp subarray tối đa 1D, trong đó A[k] = sum{B[i..j, k]}. Thông tin chi tiết chính là, đối với i cố định, nếu chúng tôi liệt kê j theo thứ tự tăng dần, chúng tôi có thể sử dụng cấu trúc dữ liệu ở trên để duy trì mảng 1D cơ bản và tìm câu trả lời rất nhanh. Các giả mô tả ý tưởng:

result = 0 
for i in (1, 2, ..., n) 
    set all fields of the binary tree T to 0 
    for j in (i, i + 1, ..., n) 
     for any k where B[j, k] != 0 
      T.update(k, A[k] + B[j, k]) 
     result = max{M[root], result} 
return result 

Giả sử ma trận chứa m yếu tố khác không, mức độ phức tạp thời gian của thuật toán này là O(mn logn). Trong trường hợp của bạn m = O(n), do đó độ phức tạp của thời gian là O(n^2 logn) và tốt hơn là O(n^3).