Click here to Skip to main content
15,919,028 members
Please Sign up or sign in to vote.
1.00/5 (2 votes)
See more:
An ordered sequence of consecutive 0 1 1 0 0 0 0 1...

Find the longest such consecutive subsequence such that there are more 1s than 0s within the subsequence

Algorithm complexity O(n2) cannot be passed

What I have tried:

Use L(k) to remember the number of 1s - number of 0s in the 1 to k subsequence
Still can't avoid the double loop, then the complexity is still quadratic.

I've looked at the internet for maximum identical substring length, maximum substring sum, and I still don't think I can apply it to this problem ......
Posted
Comments
Richard MacCutchan 17-Sep-23 11:16am    
Your assignment is not to find the answer on the internet, but to work it out for yourself.
njukenanli 17-Sep-23 11:22am    
All right, I've thought about it for a whole week. If I can figure it out myself, I won't go to the web...... Our teacher don't provide answers.
Richard MacCutchan 17-Sep-23 11:25am    
Well if the teacher provide the answer there would be nothing for you to do. The problem is essentially one of mathematics, so that is what you should focus on. Writing the code once you understand the algorithm should not be too difficult.
Patrice T 17-Sep-23 14:38pm    
Show your work so far.

Finding the optimal solution may require some thought. Maybe it is also more effort than first assumed. If I have interpreted it correctly, the longest subsequence with more ones than zeros is to be found in the given repeating number sequence "0 1 1 0 0 0 1...".

As usual, one should first know what the correct result is. For the given example, the longest subsequence with more ones than zeros seems to be the sequence "1 0 1 1 0" with a length of 5.

So since results can contain the end and the beginning of the sequence you could simplify the search by doubling the sequence first.
C++
std::string sequence = "01100001";
sequence += sequence;

Then it would be advisable to write a function that checks whether a partial sequence contains a solution. Based on simple strings it could look like this.

C++
int hasMoreOnes(const std::string& sequence, int left, int right)
{
    int ones_count = 0;
    int zeros_count = 0;
    bool valid = true;

    for (int i = left; valid && (i <= right); ++i) {
        switch (sequence[i]) {
        case '0': 
            zeros_count++; break;
        case '1':
            ones_count++; break;
        default:  
            valid = false;  // unexpected value
        }
    }

    return ones_count - zeros_count;
}

Since there are several possible locations, one could remember them and compare them at the end.
For an optimized solution, however, the comparison of the current length with the largest found length of a partial sequence is sufficient. For tracing and debugging it can be useful to output all locations. A possible solution would be to search for a current 1 in each case and to increase the range to the right and left until the condition is no longer fulfilled. The total length is then the distance between the right and left index. At the end the result can be simply written out:
C++
std::string sequence = "01100001"; // The given sequence
std::cout << "Examine sequence:" << sequence << "..." <<sequence << "\n";
std::cout << "Max. subsequence length: " << find_max_adjacent_subsequence(sequence) << std::endl;
 
Share this answer
 
While we are more than willing to help those that are stuck, that doesn't mean that we are here to do it all for you! We can't do all the work, you are either getting paid for this, or it's part of your grades and it wouldn't be at all fair for us to do it all for you.

So we need you to do the work, and we will help you when you get stuck. That doesn't mean we will give you a step by step solution you can hand in!
Start by explaining where you are at the moment, and what the next step in the process is. Then tell us what you have tried to get that next step working, and what happened when you did.

If you are having problems getting started at all, then this may help: How to Write Code to Solve a Problem, A Beginner's Guide[^]
 
Share this answer
 
Quote:
Still can't avoid the double loop, then the complexity is still quadratic.

Since you are unable to show your work, lets guess that you are using 2 nested loops and checking every substring of input.
The solution is to solve the problem by hand with a sheet of paper and a pencil.
Are you checking every single substring or your brain found a faster way ?
The answer should be "Faster way".
This 'faster way' is basically your optimized algorithm. A little thinking is becessary to translate to code.
 
Share this answer
 

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900