Longest subarray tích cực

Question

mảng A [] chỉ chứa '1' và '-1'

Thi công mảng B, trong đó B [i] là độ dài của mảng con liên tục dài nhất bắt đầu từ j và kết thúc tại i, nơi j < i and A[j] + .. + A[i] > 0

Rõ ràng O (n^2) giải pháp sẽ là:

for (int i = 0; i < A.size(); ++i) { 
    j = i-1; 
    sum = A[i]; 
    B[i] = -1; //index which fills criteria not found 
    while (j >=0) { 
     sum += A[j]; 
     if (sum > 0) 
      B[i] = i - j + 1; 
     --j; 
    } 
} 

tôi đang tìm O (n) giải pháp.

Answer 1

Bí quyết là nhận ra rằng chúng tôi chỉ cần tìm j tối thiểu sao cho (A[0] + ... + A[j-1]) == (A[0] + ... + A[i]) - 1. A[j] + ... + A[i] giống như (A[0] + ... + A[i]) - (A[0] + ... + A[j-1]), vì vậy khi chúng tôi tìm đúng j, tổng số tiền giữa j và i sẽ là 1. Bất kỳ j nào trước đó sẽ không tạo ra giá trị dương và sau đó j sẽ không cho chúng ta chuỗi dài nhất có thể. Nếu chúng tôi theo dõi vị trí đầu tiên của chúng tôi đạt được mỗi giá trị âm kế tiếp, thì chúng tôi có thể dễ dàng tra cứu giá trị j thích hợp cho bất kỳ i nào đã cho.

Đây là một C++ thực hiện:

vector<int> solve(const vector<int> &A) 
{ 
    int n = A.size(); 
    int sum = 0; 
    int min = 0; 
    vector<int> low_points; 
    low_points.push_back(-1); 
    // low_points[0] is the position where we first reached a sum of 0 
    // which is just before the first index. 
    vector<int> B(n,-1); 
    for (int i=0; i!=n; ++i) { 
     sum += A[i]; 
     if (sum<min) { 
      min = sum; 
      low_points.push_back(i); 
      // low_points[-sum] will be the index where the sum was first 
      // reached. 
     } 
     else if (sum>min) { 
      // Go back to where the sum was one less than what it is now, 
      // or go all the way back to the beginning if the sum is 
      // positive. 
      int index = sum<1 ? -(sum-1) : 0; 
      int length = i-low_points[index]; 
      if (length>1) { 
       B[i] = length; 
      } 
     } 
    } 
    return B; 
} 

Answer 2

Bạn có thể xem xét các khoản + 1/-1, giống như trên đồ thị của tôi. Chúng tôi bắt đầu lúc 0 (không quan trọng).

Vì vậy: bạn muốn, khi xem xét điểm bất cứ điều gì, để có được những ở bên trái điểm khác đó là xa nhất và dưới nó.

1 xây dựng và duy trì tổng

Phải mất n lần lặp: O (n)

2 xây dựng một giá trị bảng => điểm, iterating mỗi điểm, và giữ được nhiều nhất ở bên trái:

Bạn nhận được: 0 => a, 1 => b (không d), 2 => c (không phải e, i, k), 3 => f (không phải h), 4 => g (không phải m), 5 => n, 6 => o

Mất n lần lặp: O (N)

3 ở mỗi cấp (nói 0, 1, 2, 3, ...) => bạn giữ điểm xa nhất, đó là bên dưới nó:

mức 0 => a

mức 1 => a

etc. => nó sẽ luôn là a.

Giả sử đồ thị bắt đầu tại điểm g:

4 => g

3 => h

2 => i

5 => g

6 => g

Sau đó: nếu một điểm chỉ trên 3 (sau đó 4: dưới dạng m) => nó sẽ là h

Cũng cần có n hoạt động ở mức tối đa (chiều cao của biểu đồ chính xác).

4 lặp lại từng điểm: B [i] của bạn.

Tại mỗi điểm, giả sử h: sum = 3, bạn lấy nhiều nhất bên dưới nó (bảng hoạt động 3): trong lược đồ của tôi, nó luôn là = 0;

Giả sử đồ thị bắt đầu tại điểm g:

cho điểm

g, h, i, k => không có gì

j => i

l => i

m => h

n => g

Bạn có thể kết hợp một số thao tác trong cùng một lần lặp.