Số sản phẩm tối đa sau

Question

Tôi cần tìm sản phẩm tối đa của một dãy theo thứ tự n số nguyên. Tôi đang tìm kiếm một thuật toán, không nhất thiết phải thể hiện dưới dạng mã.

Ví dụ:

1. Trong: 3,1, -2,4. Out: 4.
2. Trong: 2,5, -1, -2, -4. Ra ngoài: 20. (2 * 5 * -1 * -2).

Tôi đã thực hiện một thuật toán trong O(n²), nhưng bây giờ tôi cần một trong O(n).
Tôi biết rằng điều đó là có thể.

Làm cách nào để thực hiện điều này trong O(n)?

Answer 1

Nếu tất cả đầu vào của bạn là> 0, sản phẩm tối đa sẽ được tìm thấy bằng cách nhân tất cả các số với nhau.

Nếu tất cả đầu vào của bạn không phải 0 và có số đếm âm, thì sản phẩm tối đa sẽ được tìm thấy bằng cách nhân tất cả các số với nhau.

Vì vậy, công việc đang xử lý số 0 và số âm.

Bạn cần phải thông qua danh sách một lần, hãy tính toán sản phẩm đang chạy khi bạn đi. Nếu bạn đạt đến 0, thì mọi thứ trước đó là một tập con ứng cử viên và các thông tin cụ thể (chỉ mục bắt đầu, chỉ mục kết thúc, sản phẩm) cần được lưu nếu nó tốt hơn so với tốt nhất cho đến nay. Bây giờ bắt đầu một sản phẩm mới chạy. Nếu bạn đạt đến số âm, mục đó là ngắt có điều kiện trong tổng số đang chạy của bạn. Sản phẩm đang chạy mà không sử dụng số âm sẽ được đánh giá là tốt nhất. Nhưng bây giờ bạn cần phải có 2 sản phẩm đang chạy, một sản phẩm có số âm và một số mới. Vì vậy, các số nhân tiếp theo cần phải làm việc với 2 danh sách. Tại thời điểm này tôi sẽ có 2 sản phẩm đang chạy. Nếu bạn nhấn một số âm khác, mỗi danh sách đang chạy của bạn cần phải chia đôi như được mô tả trước đó. Vì vậy, bạn có thể kết thúc với rất nhiều danh sách chạy nếu bạn không cắt tỉa. Tôi nghĩ rằng bạn có thể cắt giảm các danh sách đang chạy để chỉ theo dõi 3: danh sách phụ vừa mới bắt đầu, danh sách tiếp tục với số lẻ của số âm và số lẻ âm số lẻ. Bất kỳ danh sách ứng cử viên nào không phải là một phần của phép nhân đang diễn ra sẽ được đánh giá để xem nó là tốt nhất trước khi bỏ nó.

Vào cuối O của nó (n)

Answer 2

Các sản phẩm dãy tối đa của một chạy các số khác không hoặc là sản phẩm của tất cả các số (nếu có một số chẵn các số âm), hoặc đó là lớn hơn của sản phẩm của tất cả các con số sau số âm đầu tiên và sản phẩm của tất cả các số lên đến số âm cuối cùng.

Điều này cung cấp cho bạn một giải pháp O (N): ngắt chuỗi thành các số không khác và áp dụng quy tắc trong đoạn đầu tiên cho mỗi phần. Chọn tối đa các giá trị này.

C-như mã Python cho việc này:

def prod(seq, a, b): 
    r = 1 
    for i in xrange(a, b): 
     r *= seq[i] 
    return r 

def maxprodnon0(seq, a, b): 
    firstneg = -1 
    negs = 0 
    for i in xrange(a, b): 
     if seq[i] >= 0: continue 
     negs += 1 
     if firstneg < 0: 
      firstneg = i 
     lastneg = i 
    if negs % 2 == 0: return prod(seq, a, b) 
    return max(prod(seq, firstneg + 1, b), prod(seq, a, lastneg)) 

def maxprod(seq): 
    best = 0 
    N = len(seq) 
    i = 0 
    while i < N: 
     while i < N and seq[i] == 0: 
      i += 1 
     j = i 
     while j < N and seq[j] != 0: 
      j += 1 
     best = max(best, maxprodnon0(seq, i, j)) 
     i = j 
    return best 

for case in [2,5,-1,-2,-4], [1,2,0,-4,5,6,0,7,1], [1,2,0,-4,5,6,-1,-1,0,7,1]: 
    print maxprod(case)