StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p><strong>New solution:</strong> Suppose we have for n-bit input bit-array 2*n-size array to keep position of bit. So, the size of array element must have enough size to keep maximum position number. For 256 input bit array, it's needed 256x2 array of bytes (byte is enough to keep 255 - the maximum position). </p> <p>Moving from the first position of bit-array we put the position into array starting from the middle of array (index is n) using a rule:</p> <p><strong>1. Increment the position if we passed "1" bit and decrement when passed "0" bit</strong></p> <p><strong>2. When meet already initialized array element - don't change it and remember the difference between positions (current minus taken from array element) - this is a size of local maximum sequence.</strong></p> <p><strong>3. Every time we meet local maximum compare it with the global maximum and update if the latter is less.</strong></p> <p>For example: bit sequence is <strong>0,0,0,1,0,1</strong> </p> <pre><code> initial array index is n set arr[n] = 0 (position) bit 0 -> index-- set arr[n-1] = 1 bit 0 -> index-- set arr[n-2] = 2 bit 0 -> index-- set arr[n-3] = 3 bit 1 -> index++ arr[n-2] already contains 2 -> thus, local max seq is [3,2] becomes abs. maximum will not overwrite arr[n-2] bit 0 -> index-- arr[n-3] already contains 3 -> thus, local max seq is [4,3] is not abs. maximum bit 1 -> index++ arr[n-2] already contains 2 -> thus, local max seq is [5,2] is abs. max </code></pre> <p>Thus, we passing through the whole bit array only once. Does this solves the task? </p> <pre><code>input: n - number of bits a[n] - input bit-array track_pos[2*n] = {0,}; ind = n; /* start from position 1 since zero has meaning track_pos[x] is not initialized */ for (i = 1; i < n+1; i++) { if (track_pos[ind]) { seq_size = i - track_pos[ind]; if (glob_seq_size < seq_size) { /* store as interm. result */ glob_seq_size = seq_size; glob_pos_from = track_pos[ind]; glob_pos_to = i; } } else { track_pos[ind] = i; } if (a[i-1]) ind++; else ind--; } output: glob_seq_size - length of maximum sequence glob_pos_from - start position of max sequence glob_pos_to - end position of max sequence </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

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