| № | Пользователь | Рейтинг |
|---|---|---|
| 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 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | awoo | 161 |
| 2 | maomao90 | 160 |
| 3 | nor | 156 |
| 3 | atcoder_official | 156 |
| 3 | cry | 156 |
| 6 | -is-this-fft- | 155 |
| 7 | maroonrk | 154 |
| 7 | adamant | 154 |
| 9 | Petr | 146 |
| 10 | djm03178 | 145 |
Given an array { 1, 7, 7, 2,3, 7, 6,-20}. Find the longest nondecreasing contiguous sequence with substitution. we can substitute any array element with any integer such as all occurences of 7 replaced with 1. In this way new array would be { 1,1,1,2,3,1,6,-20}. Only one substitution is allowed.
What can be the optimal solution for this?
Can someone help me with the approach?
Approach- 1. Pre compute Longest Non-Decreasing Subsequence Without Substitution. 2. Store Element Positions. 3. Store Element Positions. 4. Single Pass Substitution and Check.
I think this should do the job — https://onecompiler.com/cpp/42qdrdbzd
Thanks!
I believe T.C. — Will be O(N^3) in your case which seems like a brute force. I was wondering if there is any better solution.
Any of those steps could be streamlined into $$$\mathcal{O}(n)$$$. Implementation (especially for step 4) is a pain in the a**, however.