Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>Different approach but still O(n) time and memory. Start with Neil's suggestion, treat 0 as -1.</p> <p>Notation: <code>A[0, …, N-1]</code> - your array of size <code>N</code>, <code>f(0)=0, f(x)=A[x-1]+f(x-1)</code> - a function</p> <p>If you'd plot <code>f</code>, you'll see, that what you look for are points for which <code>f(m)=f(n), m=n-2k</code> where k-positive natural. More precisely, only for <code>x</code> such that <code>A[x]!=A[x+1]</code> (and the last element in an array) you must check whether <code>f(x)</code> already occurred. Unfortunately, now I see no improvement over having array <code>B[-N+1…N-1]</code> where such information would be stored.</p> <p>To complete my thought: <code>B[x]=-1</code> initially, <code>B[x]=p</code> when <code>p = min k: f(k)=x</code> . And the algorithm is (double-check it, as I'm very tired):</p> <pre><code>fx = 0 B = new array[-N+1, …, N-1] maxlen = 0 B[0]=0 for i=1…N-1 : fx = fx + A[i-1] if B[fx]==-1 : B[fx]=i else if ((i==N-1) or (A[i-1]!=A[i])) and (maxlen &lt; i-B[fx]): We found that A[B[fx], …, i] is best than what we found so far maxlen = i-B[fx] </code></pre> <hr> <p><strong>Edit</strong>: Two bed-thoughts (= figured out while laying in bed :P ):</p> <p><strong>1)</strong> You could binary search the result by the length of subarray, which would give O(n log n) time and O(1) memory algorithm. Let's use function <code>g(x)=x - x mod 2</code> (because subarrays which sum to 0 are always of even length). Start by checking, if the whole array sums to 0. If yes -- we're done, otherwise continue. We now assume 0 as starting point (we know there's subarray of such length and "summing-to-zero property") and g(N-1) as ending point (we know there's no such subarray). Let's do</p> <pre><code> a = 0 b = g(N-1) while a&lt;b : c = g((a+b)/2) check if there is such subarray in O(n) time if yes: a = c if no: b = c return the result: a (length of maximum subarray) </code></pre> <p>Checking for subarray with "summing-to-zero property" of some given length L is simple:</p> <pre><code> a = 0 b = L fa = fb = 0 for i=0…L-1: fb = fb + A[i] while (fa != fb) and (b&lt;N) : fa = fa + A[a] fb = fb + A[b] a = a + 1 b = b + 1 if b==N: not found found, starts at a and stops at b </code></pre> <p><strong>2)</strong> …can you modify input array? If yes and if O(1) memory means exactly, that you use <em>no additional space (except for constant number of elements)</em>, then just store your prefix table values in your input array. No more space used (except for some variables) :D</p> <p>And again, double check my algorithms as I'm veeery tired and could've done off-by-one errors.</p>
    singulars
    1. This table or related slice is empty.
    1. POSpace-efficient algorithm for finding the largest balanced subarray?
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USkgadek
    1. USkgadek
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. This table or related slice is empty.
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload