1

Let's say I have a vector v with random 1 and 0.

std::vector<int> v = {1,0,1,0,0,1,0,1};

I want to find out the max sequence with the property v[i] != v[i-1]. Basically the numbers need to be different. In this example the max sequence is 4 (1, 0, 1, 0) from position v[0] to v[3]. There is also (0,1,0,1) from position v[4] to v[7]. There are 2 max sequences so the final output should look like this:

4 2

Where 4 is the max sequence and 2 the numbers of max sequences. Let's take another example:

std::vector<int> v2 = {1,0,1,1,1,0,1,0,1,0};

The output here should be: 6 1

The max sequence starts from v[4] to v[9]. There is only one max sequence so it will print 1 this time.

I tried to solve this using a for loop: n - number of integers in the vector k - number of different integers in vector maxk - the max sequence many - how many max sequence are

for(int i{1}; i < n; i++) {
    if(v[i] != v[i-1]) {
        k++;
        if(k > maxk) {
            maxk = k;
        }
    }
    else {
        if(k == maxk) {
            many++;
        }
        else {
            many = 1;
        }
        k = 1;
    }
}

But if you give it a vector like {1, 0, 0} it will not work. Can someone give me a tip of how this problem can be solved? Sorry for my bad english

sigma
  • 11
  • 2
  • 1
    You should think about the solution using paper and pencil before writing any code. If you did that, then the program becomes simple -- just mimic the steps you wrote down on paper. – PaulMcKenzie Feb 18 '23 at 14:56
  • I did that, but for me is still pretty unclear. Can you be a little bit more explicit? – sigma Feb 18 '23 at 15:07
  • Also this is more an "algorithm" question (tag) then a C++ one. Looks like a candidate for [sliding window technique](https://stackoverflow.com/questions/8269916/what-is-sliding-window-algorithm-examples) – Pepijn Kramer Feb 18 '23 at 15:07
  • What is the initial values of many? I think you cannot increment many in the else branch when k == maxk, since k is also equal to maxk, if the current sequence larger is the largest. – Fomas Feb 18 '23 at 16:17
  • The `if(k == maxk)` conditional should be part of the `v[i] != v[i-1]` case. `many = 1;` should happen when `k > maxk`. So the `v[i] == v[i-1]` case should only have `k = 1;` – paleonix Feb 18 '23 at 16:30

1 Answers1

0

First, sequence isn't the right word. A sequence can jump past elements. You mean a subarray.

Second, you talk about arrays with 0 and 1 in them, then give an example with 2. Do you want to not count subarrays with 2? Or count them? In other words if the input is [1, 2, 2] are you expecting an answer of 1 1 or 2 1?'.

That said, just make an array of where the best current subarray begins. For your first example that array would look like this:

1, 0, 1, 0, 0, 1, 0, 1
0, 0, 0, 0, 4, 4, 4, 4

And then a linear scan finds that you have a group of 4 starting at index 0, and another group of 4 starting at index 4.

For your next example,

1, 0, 1, 1, 1, 0, 1, 0, 1, 0
0, 0, 0, 3, 4, 4, 4, 4, 4, 4

And you have a group of 3 starting at index 0, 1 starting at 3, and 6 starting at 4. So we've found the 1 group of 6.

For your last example, what you'd get would depend on the answer you want.

I'll leave coding this to you.

btilly
  • 43,296
  • 3
  • 59
  • 88