This takes input n (number of bits) and then the n bits (separated by spaces). It prints the beginning position and length of the largest and second largest run's of 1's, incuding a run that "wraps" around from the end to the beginning (which would end up having position + length >= n).
It still seems more complicated than necessary! (Although the Record object is mostly boilerplate and is totally basic.)
Code:
#include <iostream>
using std::cout;
using std::cin;
struct Record {
int pos, len;
Record(int p=0, int n=0) : pos(p), len(n) {}
void set(int p=0, int n=0) { pos = p; len = n; }
Record& operator++() { ++len; return *this; }
Record operator+=(const Record& rhs) { len += rhs.len; return *this; }
operator bool() { return len > 0; }
bool operator!() { return len <= 0; }
bool operator>(const Record& rhs) { return len > rhs.len; }
friend std::ostream& operator<<(std::ostream& os, const Record& r) {
return os << '[' << r.pos << ',' << r.len << ']';
}
};
void place(Record& cur, Record& a, Record& b) { // Places cur into a, b
if (cur > a) { b = a; a = cur; }
else if (cur > b) b = cur;
cur.set(); // reset cur
}
int main() {
int n = 0; // length of input sequence
cin >> n;
// Read initial bits. "Placing" of an initial run is deferred
// as it may need to be added to a terminal run.
int i = 0, bit = 1;
for ( ; i < n && bit; ++i)
cin >> bit;
// Initial run length is usually i - 1 unless the sequence
// was all 1's, in which case bit will be 1 instead of 0 here.
Record a, b, cur, init(0, i - !bit);
for ( ; i < n; ++i) {
cin >> bit;
if (bit) {
if (!cur) // beginning of a run
cur.set(i); // so save start position
++cur; // increment length
}
else if (cur)
place(cur, a, b);
}
if (init) { // If we have an initial run
if (cur) // and also a terminal run
cur += init; // add them together
else
place(init, a, b); // otherwise, process initial run normally
}
if (cur)
place(cur, a, b); // process terminal run
cout << a << " : " << b << '\n';
}
Anyway, if your's is finding the streaks properly then you probably aren't interested in it. But it does demonstrate that it can be done more simply.
I've thought of some points about k:
If there was only a single streak of 1's (b.len == 0) then the answer for all queries is min(a.len, k)
Otherwise if a.len and b.len are both >= k then the answer for all queries is k
Otherwise, if a.len == b.len, then the answer for all queries is min(a.len, k)
Otherwise you need to process the queries.
For each query:
* if the current "first" element doesn't split a then the answer is min(a.len, k)
* otherwise the answer is either one of the a's parts, or b (or k, of course).