Find maximum length of subsequence of an array where odd and even index of subsequence having same element in ### o(n*n) for eg. array=[1,2,8,1,2,8,2] maximum length of subsequence if 2,8,2,8,2
# | User | Rating |
---|---|---|
1 | tourist | 3947 |
2 | jiangly | 3734 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | ecnerwala | 3581 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | ksun48 | 3479 |
# | User | Contrib. |
---|---|---|
1 | awoo | 162 |
2 | maomao90 | 160 |
3 | nor | 156 |
3 | adamant | 156 |
5 | -is-this-fft- | 155 |
5 | atcoder_official | 155 |
7 | maroonrk | 153 |
7 | cry | 153 |
9 | SecondThread | 147 |
10 | Petr | 146 |
Find maximum length of subsequence of an array where odd and even index of subsequence having same element in ### o(n*n) for eg. array=[1,2,8,1,2,8,2] maximum length of subsequence if 2,8,2,8,2
Name |
---|
I think this can be solved using : create two buckets(vars) and xor the odd indices and even indices. starting from 0 and 1 , move to next set of elements and again xor the odd with the odd bucket and even with the ven bucket and if any of them doesnt turn to zero or the same number remove the previous element and put in new element. tc: o(n) my explanation is bit vague but ill try to dry run on your example
say a =1 b =2; now starting from index 2 — > 8^a since the value doesnt become zero discard 1 and make a = 8 3-> 1^b since non zero discard previous value and set b= 1 and so on ... you also reset count =2 everytime you discard stuff and the when you dont discard a element you basically increment the count and save the max count.
...
I will share my solution of complexity O(N^2) assuming each element is from 0 to n — 1 inclusive.
Considering the case when the odd and even positions have equal values, we can say that the answer is atleast equal to the frequency of the most frequent element.
Now the case, when the odd and even position elements have different values, we have to iterate over all possible values at the odd index of the sub-sequence in the array (that is from 0 to n — 1) and calculate the best possible length with such an element at the odd positions as follows:
We need to find optimal even position element for every possible odd position element.
Let this odd position element be called o and the optimal even position element for o be e.
Please try to visualise how to find e for a given o:
Colour all occurrences of o in the array to yellow. To maintain invariance we will have to add two elements in the array one at beginning and other at end that is at positions -1 and n (0-based) which will be marked yellow irrespective.
Now consider segments between these marked yellow cells. Colour all the first occurrences of each element in every segment as red.
The optimal even position element i.e. e is the value which is coloured red the most. And the length of the sub-sequence is the length of the alternating cells of o and e.
We find optimal length of the sub-sequence for each o(0 to n — 1) by the above algorithm.
Answer is the maximum length amoung all such possible lengths.
did you check my o(n) solution?